Problem Description

Given an integer N, count how many numbers in the range [1, N] are confusing numbers. A confusing number is a number that, when rotated 180 degrees, becomes a different valid number with each digit still valid after rotation.

The valid digits and their rotated mappings are:

• 0 → 0
• 1 → 1
• 6 → 9
• 8 → 8
• 9 → 6

A number is confusing if after rotating each digit and reversing the order, the resulting number is both valid and different from the original.

Constraints:

• 1 ≤ N ≤ 10⁹
• Digits used: only 0, 1, 6, 8, 9 (other digits are invalid)
• No leading zeros

Thought Process

The task is to count numbers up to N that are confusing. A brute-force approach would check every number from 1 to N, but this is too slow for large N.

We realize that only numbers containing the digits 0, 1, 6, 8, 9 can possibly be confusing. To optimize, we can generate numbers using only these digits, similar to generating numbers in a specific base. For each generated number, we check if its rotated version is valid and different from the original.

This approach avoids checking numbers with invalid digits, greatly reducing the search space. We can use a recursive depth-first search (DFS) to build numbers digit by digit, pruning impossible branches early.

Solution Approach

The solution uses a recursive DFS to generate all valid numbers up to N using only the digits 0, 1, 6, 8, and 9. At each step, we:

• Start from 0 and build numbers by appending allowed digits.
• Skip numbers with leading zeros (except for 0 itself).
• For each generated number (excluding 0), check if it is a confusing number:
  • Rotate it by mapping each digit and reversing the order.
  • If the rotated number is different from the original, count it as confusing.
• Stop recursion when the number exceeds N.

This method ensures that we only generate and check numbers that could possibly be confusing, making the approach efficient even for large N.

Example Walkthrough

Let's consider N = 20:

• We generate numbers: 1, 6, 8, 9, 10, 11, 16, 18, 19
• Check each number:
  • 6 → rotates to 9 (confusing)
  • 9 → rotates to 6 (confusing)
  • 10 → rotates to 01 = 1 (confusing)
  • 16 → rotates to 91 (confusing)
  • 18 → rotates to 81 (confusing)
  • 19 → rotates to 61 (confusing)
• Numbers like 1, 8, 11 are not confusing because their rotated forms are the same as the original.
• So, the answer is 6 for N = 20.

Time and Space Complexity

Brute-force approach: O(N log N), since we check every number up to N and each check takes O(log N) time (due to digit manipulation).

Optimized DFS approach: The number of numbers composed only of [0,1,6,8,9] up to N is much less than N. The time complexity is O(K), where K is the count of such numbers ≤ N, each requiring O(L) time for the rotation check (L = number of digits). In practice, this is efficient as K is much smaller than N.

Space complexity is O(L) for the recursion stack, where L is the maximum length of N in digits.

Summary

We efficiently count confusing numbers up to N by generating only valid candidates using DFS and checking each one. The key insight is to avoid brute-force by leveraging the restricted digit set, resulting in a solution that is both elegant and scalable.

Code 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]
        self.count = 0

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

        def dfs(num):
            if num > N:
                return
            if num != 0 and is_confusing(num):
                self.count += 1
            for d in digits:
                if num == 0 and d == 0:
                    continue
                next_num = num * 10 + d
                if next_num > N:
                    continue
                dfs(next_num)

        dfs(0)
        return self.count
      

class Solution {
public:
    int confusingNumberII(int N) {
        unordered_map<int, int> rotate = {{0,0}, {1,1}, {6,9}, {8,8}, {9,6}};
        vector<int> digits = {0,1,6,8,9};
        int count = 0;

        function<bool(int)> is_confusing = [&](int num) {
            int original = num, rotated = 0;
            while (num > 0) {
                int d = num % 10;
                rotated = rotated * 10 + rotate[d];
                num /= 10;
            }
            return rotated != original;
        };

        function<void(long)> dfs = [&](long num) {
            if (num > N) return;
            if (num != 0 && is_confusing(num)) count++;
            for (int d : digits) {
                if (num == 0 && d == 0) continue;
                long next_num = num * 10 + d;
                if (next_num > N) continue;
                dfs(next_num);
            }
        };

        dfs(0);
        return count;
    }
};
      

class Solution {
    int[] digits = {0, 1, 6, 8, 9};
    Map<Integer, Integer> rotate = Map.of(0,0, 1,1, 6,9, 8,8, 9,6);
    int count = 0;

    public int confusingNumberII(int N) {
        dfs(0, N);
        return count;
    }

    private void dfs(long num, int N) {
        if (num > N) return;
        if (num != 0 && isConfusing(num)) count++;
        for (int d : digits) {
            if (num == 0 && d == 0) continue;
            long next = num * 10 + d;
            if (next > N) continue;
            dfs(next, N);
        }
    }

    private boolean isConfusing(long num) {
        long original = num, rotated = 0;
        while (num > 0) {
            int d = (int)(num % 10);
            rotated = rotated * 10 + rotate.get(d);
            num /= 10;
        }
        return rotated != original;
    }
}
      

var confusingNumberII = function(N) {
    const rotate = {0:0, 1:1, 6:9, 8:8, 9:6};
    const digits = [0,1,6,8,9];
    let count = 0;

    function isConfusing(num) {
        let original = num, rotated = 0;
        while (num > 0) {
            let d = num % 10;
            rotated = rotated * 10 + rotate[d];
            num = Math.floor(num / 10);
        }
        return rotated !== original;
    }

    function dfs(num) {
        if (num > N) return;
        if (num !== 0 && isConfusing(num)) count++;
        for (let d of digits) {
            if (num === 0 && d === 0) continue;
            let next = num * 10 + d;
            if (next > N) continue;
            dfs(next);
        }
    }

    dfs(0);
    return count;
};