Confusing Number II — LeetCode 1088 Python Solution
HardLeetCode PremiumMathBacktracking
- Problem
- #1088
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid. We can rotate digits of a number by 180 degrees to form new digits.
Example
- Input
- n = 20
- Output
- 6
- Explanation
- The confusing numbers are [6,9,10,16,18,19].
Python solution
Python
class Solution:
def confusingNumberII(self, n: int) -> int:
def check(x: int) -> bool:
y, t = 0, x
while t:
t, v = divmod(t, 10)
y = y * 10 + d[v]
return x != y
def dfs(pos: int, limit: bool, x: int) -> int:
if pos >= len(s):
return int(check(x))
up = int(s[pos]) if limit else 9
ans = 0
for i in range(up + 1):
if d[i] != -1:
ans += dfs(pos + 1, limit and i == up, x * 10 + i)
return ans
d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
s = str(n)
return dfs(0, True, 0)Complexity
| Measure | Complexity |
|---|---|
| Time | Exponential (worst case) |
| Space | O(depth) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1088. Confusing Number II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1088. Confusing Number II?
- LeetCode 1088. Confusing Number II is rated Hard on LeetCode.
- What topics does LeetCode 1088. Confusing Number II cover?
- LeetCode 1088. Confusing Number II is tagged Math and Backtracking on LeetCode.
- Is LeetCode 1088. Confusing Number II a premium problem?
- Yes. LeetCode 1088. Confusing Number II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.