LeetCode 1088 - Confusing Number II

In this problem, we are given an integer n, and we must count how many numbers in the range [1, n] are considered confusing numbers. A number becomes a confusing number if, after rotating every digit by 180 degrees, the resulting number is both: 1. Valid after rotation 2.

leetcodehardmathbacktracking

LeetCode Problem 1088

Difficulty: 🔴 Hard
Topics: Math, Backtracking

Solution

Problem Understanding

In this problem, we are given an integer n, and we must count how many numbers in the range [1, n] are considered confusing numbers.

A number becomes a confusing number if, after rotating every digit by 180 degrees, the resulting number is both:

  1. Valid after rotation
  2. Different from the original number

Only five digits remain valid after rotation:

Original Rotated
0 0
1 1
6 9
8 8
9 6

Digits 2, 3, 4, 5, and 7 are invalid because they do not form recognizable digits after rotation.

The rotation process also reverses digit positions naturally. For example:

  • 16 becomes 91
  • 89 becomes 68
  • 8000 becomes 0008, which is treated as 8

The task is not to generate the rotated numbers themselves, but to count how many valid confusing numbers exist from 1 through n.

The constraint 1 <= n <= 10^9 is very important. Since n can be as large as one billion, iterating through every number and checking whether it is confusing may become expensive. A smarter generation strategy is required.

Several edge cases are important:

  • Numbers containing invalid digits must immediately be rejected.
  • Numbers like 11, 88, or 69 rotate into themselves and are therefore not confusing.
  • Leading zeros after rotation must be ignored correctly.
  • The number 0 itself is not included because the range starts from 1.

Approaches

Brute Force Approach

The most straightforward solution is to iterate through every integer from 1 to n.

For each number:

  1. Extract every digit.
  2. Verify that all digits are rotatable.
  3. Build the rotated number by reversing digit order and applying the rotation mapping.
  4. Compare the rotated number with the original number.
  5. Count it if they differ.

This approach is correct because it explicitly checks every possible candidate.

However, it is inefficient. If n = 10^9, we may need to inspect one billion numbers. Even though each check only takes O(log n) time, the total runtime becomes far too large.

Optimal Approach, Backtracking Generation

The key observation is that only numbers composed of digits {0,1,6,8,9} can possibly be valid.

Instead of checking all numbers from 1 to n, we generate only numbers that contain valid digits.

This dramatically reduces the search space.

For example:

  • A 9 digit number normally has 10^9 possibilities.
  • Using only 5 valid digits gives at most 5^9 = 1,953,125 possibilities.

This is much smaller and manageable.

We use depth first search (DFS) or backtracking to construct valid numbers digit by digit.

For each generated number:

  1. Ensure it does not exceed n
  2. Check whether its rotated form differs from the original
  3. Count it if confusing
  4. Continue extending it with more valid digits

This avoids exploring impossible candidates entirely.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(log n) Checks every number individually
Optimal O(5^d × d) O(d) Generates only valid candidates, where d is number of digits

Since n <= 10^9, the maximum number of digits is 10, making the backtracking solution efficient.

Algorithm Walkthrough

Step 1, Store Valid Rotations

We first define the rotation mapping:

{
    0: 0,
    1: 1,
    6: 9,
    8: 8,
    9: 6
}

This allows us to rotate any valid digit efficiently.

Step 2, Define DFS Generation

We recursively build numbers using only valid digits.

At every recursive call:

  • We have a partially built number
  • We try appending one more valid digit
  • We stop if the number exceeds n

This ensures all generated numbers are potentially valid after rotation.

Step 3, Skip Leading Zero

We never start a number with 0.

Otherwise we would generate duplicates such as:

  • 01
  • 001
  • 0001

All of these represent the same number.

Step 4, Check Whether a Number Is Confusing

For each generated number:

  1. Rotate every digit
  2. Reverse digit order
  3. Construct the rotated number
  4. Compare against the original

If the rotated number differs, the number is confusing.

Step 5, Continue Recursion

After processing the current number, continue appending more digits recursively.

This explores the entire valid search space.

Why it works

The algorithm generates every number that could possibly be valid after rotation because it uses only rotatable digits.

No valid candidate is missed because DFS explores every combination of valid digits up to n.

No invalid candidate is included because numbers containing invalid digits are never generated.

The confusion check guarantees we count only numbers whose rotated form differs from the original.

Therefore, the algorithm correctly counts all confusing numbers in [1, n].

Python Solution

class Solution:
    def confusingNumberII(self, n: int) -> int:
        rotation = {
            0: 0,
            1: 1,
            6: 9,
            8: 8,
            9: 6
        }

        valid_digits = [0, 1, 6, 8, 9]

        def is_confusing(num: int) -> bool:
            original = num
            rotated = 0

            while num > 0:
                digit = num % 10
                rotated = rotated * 10 + rotation[digit]
                num //= 10

            return rotated != original

        def dfs(current: int) -> int:
            count = 0

            if current > n:
                return 0

            if current != 0 and is_confusing(current):
                count += 1

            for digit in valid_digits:
                if current == 0 and digit == 0:
                    continue

                next_number = current * 10 + digit

                if next_number <= n:
                    count += dfs(next_number)

            return count

        return dfs(0)

The solution begins by storing the rotation mapping and the list of valid digits.

The is_confusing() helper function computes the rotated version of a number. It processes digits from right to left and builds the rotated number incrementally.

For example:

  • 16
  • Process 6 → 9
  • Process 1 → 1
  • Result becomes 91

The DFS function generates all valid numbers recursively.

The recursion starts from 0, but 0 itself is never counted.

For every generated number:

  1. If it exceeds n, recursion stops.
  2. If it is confusing, increment the answer.
  3. Append every valid digit and continue searching.

The leading zero check prevents duplicate constructions.

Because only valid digits are used, every generated number is guaranteed rotatable.

Go Solution

func confusingNumberII(n int) int {
    rotation := map[int]int{
        0: 0,
        1: 1,
        6: 9,
        8: 8,
        9: 6,
    }

    validDigits := []int{0, 1, 6, 8, 9}

    var isConfusing func(int) bool

    isConfusing = func(num int) bool {
        original := num
        rotated := 0

        for num > 0 {
            digit := num % 10
            rotated = rotated*10 + rotation[digit]
            num /= 10
        }

        return rotated != original
    }

    var dfs func(int) int

    dfs = func(current int) int {
        if current > n {
            return 0
        }

        count := 0

        if current != 0 && isConfusing(current) {
            count++
        }

        for _, digit := range validDigits {
            if current == 0 && digit == 0 {
                continue
            }

            nextNumber := current*10 + digit

            if nextNumber <= n {
                count += dfs(nextNumber)
            }
        }

        return count
    }

    return dfs(0)
}

The Go implementation closely mirrors the Python solution.

The main difference is that Go uses explicit function variables for recursive closures.

The rotation mapping is implemented using map[int]int, and the DFS recursion returns the count accumulated from all branches.

Go integers safely handle the problem constraints because n <= 10^9.

Worked Examples

Example 1

Input: n = 20

The DFS generates numbers using digits {0,1,6,8,9}.

Generated numbers up to 20:

Number Rotated Confusing?
1 1 No
6 9 Yes
8 8 No
9 6 Yes
10 1 Yes
11 11 No
16 91 Yes
18 81 Yes
19 61 Yes

Total confusing numbers:

6

Example 2

Input: n = 100

Generated confusing numbers:

Number Rotated
6 9
9 6
10 1
16 91
18 81
19 61
60 9
61 19
66 99
68 89
80 8
81 18
86 98
89 68
90 6
91 16
98 86
99 66
100 1

Total:

19

Complexity Analysis

Measure Complexity Explanation
Time O(5^d × d) Generates all valid digit combinations
Space O(d) DFS recursion depth

Here, d is the number of digits in n.

For n <= 10^9, d <= 10.

The DFS generates at most:

5^1 + 5^2 + ... + 5^10

numbers, which is manageable.

Each confusion check takes O(d) time because we process each digit once.

The recursion stack depth is at most the number of digits.

Test Cases

sol = Solution()

assert sol.confusingNumberII(1) == 0       # no confusing numbers
assert sol.confusingNumberII(6) == 1       # only 6
assert sol.confusingNumberII(9) == 2       # 6 and 9
assert sol.confusingNumberII(10) == 3      # includes 10
assert sol.confusingNumberII(20) == 6      # provided example
assert sol.confusingNumberII(100) == 19    # provided example

assert sol.confusingNumberII(11) == 3      # 11 rotates to itself
assert sol.confusingNumberII(69) == 10     # includes many two-digit cases
assert sol.confusingNumberII(88) == 11     # 88 is not confusing
assert sol.confusingNumberII(99) == 18     # 99 rotates to 66
assert sol.confusingNumberII(1000) > 0     # larger boundary
assert sol.confusingNumberII(1000000000) > 0  # maximum constraint stress test

Test Summary

Test Why
n = 1 Smallest possible input
n = 6 Single confusing number
n = 9 Multiple single digit confusing numbers
n = 10 Leading zero after rotation
n = 20 Provided example
n = 100 Provided example
n = 11 Number rotating to itself
n = 69 Multi digit rotation behavior
n = 88 Symmetric non confusing number
n = 99 Rotated number changes completely
n = 1000 Larger recursive generation
n = 10^9 Maximum constraint stress test

Edge Cases

One important edge case is numbers that rotate into themselves. Examples include 1, 8, 11, and 69. A naive implementation might incorrectly count them simply because they contain valid digits. The algorithm avoids this by explicitly constructing the rotated value and checking whether it differs from the original number.

Another important case involves leading zeros after rotation. For example, 10 rotates into 01, which should be interpreted as 1. If the implementation compared digit strings directly, it might incorrectly treat "01" differently from 1. The numeric construction naturally removes leading zeros, so the comparison remains correct.

A third important edge case is preventing numbers with leading zeros during DFS generation. Without this restriction, the recursion could generate duplicates like 01, 001, and 0001. The implementation prevents this by skipping digit 0 when constructing the first digit of a number.

Finally, the upper constraint n = 10^9 requires careful pruning. The DFS immediately stops recursion whenever the current number exceeds n, ensuring the algorithm remains efficient even at the maximum input size.