Problem statement

https://leetcode.com/problems/confusing-number-ii

Solution

We can generate all numbers which have only digits $0, 1, 6, 8, 9$ and then check if they are confusing.

We can do optimization: let dfs(num, num_rot, power) be our backtracking function, where num is number with digits $0, 1, 6, 8, 9$, num_rot is rotated number, power 10 to the power of number of digits in our number. We need it for faster updates. Then on each step we try to add one digit to the end of num, and quickly compute new num_rot. Finally, we run function for all possible start $1, 6, 8, 9$.

Complexity

Time complexity is $O(5^k)$, where $k$ is number of digits in $N$, space complexity is $O(k)$ to keep recursion stack.

Code

class Solution:
    def confusingNumberII(self, N):
        map = {0:0, 1:1, 6:9, 8:8, 9:6}
        self.ans = 0
        def dfs(num, num_rot, power):
            if num > N: return
            if num != num_rot: self.ans += 1
            for v in map.keys():
                dfs(num*10 + v, power*map[v] + num_rot, 10*power)

        for i in map.keys():
            if i == 0: continue
            dfs(i, map[i], 10)

        return self.ans

There is also digit build technique, but it is quite painful to code.