Input: n =20Output: 6Explanation: The confusing numbers are [6,9,10,16,18,19].6 converts to 9.9 converts to 6.10 converts to 01 which is just 1.16 converts to 91.18 converts to 81.19 converts to 61.
Example 2:
1
2
3
Input: n =100Output: 19Explanation: The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
We want to count all numbers in [1, n] that are confusing numbers. A confusing number is one that, when rotated 180 degrees, becomes a different valid number. We can use backtracking to generate all valid numbers up to n using only valid digits, and count those that are confusing.
classSolution {
funconfusingNumberII(n: Int): Int {
val digits = listOf(0, 1, 6, 8, 9)
val mp = mapOf(0 to 0, 1 to 1, 6 to 9, 8 to 8, 9 to 6)
var ans = 0fundfs(x: Long) {
if (x > n) returnif (x !=0L&& isConfusing(x, mp)) ans++for (d in digits) {
if (x ==0L&& d ==0) continueval nx = x * 10 + d
if (nx > n) break dfs(nx)
}
}
dfs(0)
return ans
}
funisConfusing(x: Long, mp: Map<Int, Int>): Boolean {
var orig = x
var rot = 0Lvar y = x
while (y > 0) {
rot = rot * 10 + mp[(y % 10).toInt()]!! y /=10 }
return rot != orig
}
}
classSolution:
defconfusingNumberII(self, n: int) -> int:
mp = {0:0, 1:1, 6:9, 8:8, 9:6}
ans =0defis_confusing(x: int) -> bool:
orig, rot = x, 0while x >0:
rot = rot *10+ mp[x %10]
x //=10return rot != orig
defdfs(x: int):
nonlocal ans
if x > n:
returnif x !=0and is_confusing(x):
ans +=1for d in [0, 1, 6, 8, 9]:
if x ==0and d ==0:
continue nx = x *10+ d
if nx > n:
break dfs(nx)
dfs(0)
return ans
⏰ Time complexity: O(log n * 5^log n), since we generate all numbers up to n using 5 digits, and each number takes O(log n) to check if it is confusing.
🧺 Space complexity: O(log n), for the recursion stack.