LeetCode Solutions
1088. Confusing Number II
Time: $O(5^{\log n})$ Space: $O(\log n)$
class Solution {
public:
int confusingNumberII(int n) {
return dfs(n, 0, 0, 1);
}
private:
vector<pair<int, 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;
// 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;
}
};
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;
}
}
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)