# 1088. Confusing Number II

• Time: $O(5^{\log n})$
• Space: $O(\log n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int confusingNumberII(int n) { return dfs(n, 0, 0, 1); } private: vector> digitToRotated{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}}; int dfs(int n, long num, long rotatedNum, long unit) { int ans = num != rotatedNum; // add one more digit for (const auto& [digit, rotated] : digitToRotated) { if (digit == 0 && num == 0) continue; const long nextNum = num * 10 + digit; if (nextNum > n) break; ans += dfs(n, nextNum, rotated * unit + rotatedNum, unit * 10); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int confusingNumberII(int n) { return dfs(n, 0, 0, 1); } private int[][] digitToRotated = {{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}}; int dfs(int n, long num, long rotatedNum, long unit) { int ans = num == rotatedNum ? 0 : 1; // add one more digit for (int[] pair : digitToRotated) { final int digit = pair[0]; final int rotated = pair[1]; if (digit == 0 && num == 0) continue; final long nextNum = num * 10 + digit; if (nextNum > n) break; ans += dfs(n, nextNum, rotated * unit + rotatedNum, unit * 10); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def confusingNumberII(self, n: int) -> int: digitToRotated = [(0, 0), (1, 1), (6, 9), (8, 8), (9, 6)] def dfs(num: int, rotatedNum: int, unit: int) -> int: ans = 0 if num == rotatedNum else 1 # add one more digit for digit, rotated in digitToRotated: if digit == 0 and num == 0: continue nextNum = num * 10 + digit if nextNum > n: break ans += dfs(nextNum, rotated * unit + rotatedNum, unit * 10) return ans return dfs(0, 0, 1)