Problem statement

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

Solution

There is straightforward solution with O(n log n) complexity, where for every number we just check if it is good or not.

Complexity

It is O(n log n) for time and O(log n) for space.

Code

class Solution:
    def rotatedDigits(self, N):
        d1, d2 = set(["0","1","2","5","6","8","9"]), set(["0","1","8"])
        ans = 0
        
        for i in range(1, N+1):
            q = set(str(i))
            ans += (int(not(q - d1)) - int(not(q - d2)))
            
        return ans

Remark

There is also O(log n) solution, if we use I call it Digits Build strategy: imagine we have N = 314792, than all numbers which are less or equal to N can be split into groups: 31479?, 3147?*, 314?**, 31?***, 3?****, ?*****, *****, ****, ***, **, *, where * means any digit and ? means digit less than digit on corresponding place in original number.