# 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

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Count of confusing numbers in `[1, n]` |

Function shape:

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

## Examples

Example 1:

```python
n = 20
```

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

Answer:

```python
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

```python
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

```python
def run_tests():
    s = Solution()

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

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `n=20` | `6` | `6,9,10,16,18,19` |
| `n=100` | `19` | More confusing numbers |