LeeCode 788. Rotated Digits

Question: https://leetcode.com/problems/rotated-digits

The below solution is slow and uses lots of space when compared to other correct solutions submitted to LeetCode. The get_digit process is O(logN), and we have to iterate through all integers up to N, so the overall efficiency is O(NlogN). I would think this already achieves the highest efficiency asymptotically. I will come back to this problem, and see where I got it wrong.

class Solution(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        rotation_map = {0:0, 1:1, 8:8, 2:5, 5:2, 6:9, 9:6}
        
        def get_digits(k):
            digits = []
            while k // 10!=0:
                digits.append(k % 10)
                k //= 10
            digits.append(k % 10)
            return digits
        
        count = 0
        for i in range(1, N+1):
            digits = get_digits(i)
            all_same = True
            for digit in digits:
                if digit not in rotation_map:
                    all_same=True # Setting this to true force the later check to fail and 
                    # avoid counting this digit
                    break
                elif digit not in (0,1,8):
                    all_same = False
                else:
                    continue
                    
            if not all_same:
                count += 1
        return count