LeetCode 1088: Confusing Number II

Problem Restatement

A confusing number rotated 180 degrees gives a different valid number (see LeetCode 1056).

Valid digit rotations: 0→0, 1→1, 6→9, 8→8, 9→6.

We are given a positive integer n.

Count all confusing numbers in [1, n].

The official constraints state that 1 <= n <= 10^9.

Input and Output

Function shape:

def confusingNumberII(n: int) -> int:
    ...

Examples

Example 1:

n = 20

Confusing numbers: 6, 9, 10, 16, 18, 19.

Answer:

6

Key Insight

Build all valid numbers using only digits {0, 1, 6, 8, 9} up to n using digit backtracking. For each valid number, check if it is confusing (rotated differs from original).

Algorithm

Backtrack by building numbers digit by digit:

1. For each valid digit, extend the current number.
2. If the number exceeds n, stop.
3. Check if the current number is confusing.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def confusingNumberII(self, n: int) -> int:
        rotate = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
        digits = [0, 1, 6, 8, 9]
        count = 0

        def is_confusing(num):
            original = num
            rotated = 0
            while num > 0:
                rotated = rotated * 10 + rotate[num % 10]
                num //= 10
            return rotated != original

        def backtrack(current):
            nonlocal count
            if current > n:
                return
            if current > 0 and is_confusing(current):
                count += 1
            for d in digits:
                if current == 0 and d == 0:
                    continue
                backtrack(current * 10 + d)

        backtrack(0)
        return count

Testing

def run_tests():
    s = Solution()

    assert s.confusingNumberII(20) == 6
    assert s.confusingNumberII(100) == 19

    print("all tests passed")

run_tests()