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.

  • When 0, 1, 6, 8, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively.
  • When 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid.

Note that after rotating a number, we can ignore leading zeros.

  • For example, after rotating 8000, we have 0008 which is considered as just 8.

Given an integer n, return _the number ofconfusing numbers in the inclusive range _[1, n].

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input: n = 20
Output: 6
Explanation: The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

Example 2:

1
2
3

Input: n = 100
Output: 19
Explanation: The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].

Constraints:

  • 1 <= n <= 10^9

Solution

Method 1 – Backtracking with Digit Mapping

Intuition

We want to count all numbers in [1, n] that are confusing numbers. A confusing number is one that, when rotated 180 degrees, becomes a different valid number. We can use backtracking to generate all valid numbers up to n using only valid digits, and count those that are confusing.

Approach

  1. Define the valid digit mapping: 0→0, 1→1, 6→9, 8→8, 9→6.
  2. Use backtracking to build numbers by appending valid digits, skipping leading zeros.
  3. For each number, check if its rotated version is valid and different from the original.
  4. Count such numbers.
  5. Start with each valid non-zero digit and recursively build larger numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int confusingNumberII(int n) {
        vector<int> digits = {0, 1, 6, 8, 9};
        unordered_map<int, int> mp = {{0,0},{1,1},{6,9},{8,8},{9,6}};
        int ans = 0;
        function<void(long)> dfs = [&](long x) {
            if (x > n) return;
            if (isConfusing(x, mp) && x != 0) ++ans;
            for (int d : digits) {
                if (x == 0 && d == 0) continue;
                long nx = x * 10 + d;
                if (nx > n) break;
                dfs(nx);
            }
        };
        dfs(0);
        return ans;
    }
    bool isConfusing(long x, unordered_map<int, int>& mp) {
        long orig = x, rot = 0;
        while (x > 0) {
            int d = x % 10;
            rot = rot * 10 + mp[d];
            x /= 10;
        }
        return rot != orig;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func ConfusingNumberII(n int) int {
    digits := []int{0, 1, 6, 8, 9}
    mp := map[int]int{0:0, 1:1, 6:9, 8:8, 9:6}
    var ans int
    var dfs func(x int)
    dfs = func(x int) {
        if x > n { return }
        if x != 0 && isConfusing(x, mp) { ans++ }
        for _, d := range digits {
            if x == 0 && d == 0 { continue }
            nx := x*10 + d
            if nx > n { break }
            dfs(nx)
        }
    }
    dfs(0)
    return ans
}
func isConfusing(x int, mp map[int]int) bool {
    orig, rot := x, 0
    for x > 0 {
        rot = rot*10 + mp[x%10]
        x /= 10
    }
    return rot != orig
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int confusingNumberII(int n) {
        int[] digits = {0, 1, 6, 8, 9};
        int ans = 0;
        Map<Integer, Integer> mp = Map.of(0,0,1,1,6,9,8,8,9,6);
        ans = dfs(0, n, digits, mp);
        return ans;
    }
    int dfs(long x, int n, int[] digits, Map<Integer, Integer> mp) {
        int cnt = 0;
        if (x > n) return 0;
        if (x != 0 && isConfusing(x, mp)) cnt++;
        for (int d : digits) {
            if (x == 0 && d == 0) continue;
            long nx = x * 10 + d;
            if (nx > n) break;
            cnt += dfs(nx, n, digits, mp);
        }
        return cnt;
    }
    boolean isConfusing(long x, Map<Integer, Integer> mp) {
        long orig = x, rot = 0;
        while (x > 0) {
            rot = rot * 10 + mp.get((int)(x % 10));
            x /= 10;
        }
        return rot != orig;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    fun confusingNumberII(n: Int): Int {
        val digits = listOf(0, 1, 6, 8, 9)
        val mp = mapOf(0 to 0, 1 to 1, 6 to 9, 8 to 8, 9 to 6)
        var ans = 0
        fun dfs(x: Long) {
            if (x > n) return
            if (x != 0L && isConfusing(x, mp)) ans++
            for (d in digits) {
                if (x == 0L && d == 0) continue
                val nx = x * 10 + d
                if (nx > n) break
                dfs(nx)
            }
        }
        dfs(0)
        return ans
    }
    fun isConfusing(x: Long, mp: Map<Int, Int>): Boolean {
        var orig = x
        var rot = 0L
        var y = x
        while (y > 0) {
            rot = rot * 10 + mp[(y % 10).toInt()]!!
            y /= 10
        }
        return rot != orig
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def confusingNumberII(self, n: int) -> int:
        mp = {0:0, 1:1, 6:9, 8:8, 9:6}
        ans = 0
        def is_confusing(x: int) -> bool:
            orig, rot = x, 0
            while x > 0:
                rot = rot * 10 + mp[x % 10]
                x //= 10
            return rot != orig
        def dfs(x: int):
            nonlocal ans
            if x > n:
                return
            if x != 0 and is_confusing(x):
                ans += 1
            for d in [0, 1, 6, 8, 9]:
                if x == 0 and d == 0:
                    continue
                nx = x * 10 + d
                if nx > n:
                    break
                dfs(nx)
        dfs(0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn confusing_number_ii(n: i32) -> i32 {
        let digits = [0, 1, 6, 8, 9];
        let mp = [(0,0),(1,1),(6,9),(8,8),(9,6)];
        let mut map = std::collections::HashMap::new();
        for (k,v) in mp.iter() { map.insert(*k, *v); }
        fn is_confusing(mut x: i64, map: &std::collections::HashMap<i32,i32>) -> bool {
            let orig = x;
            let mut rot = 0;
            while x > 0 {
                rot = rot * 10 + map[&((x % 10) as i32)] as i64;
                x /= 10;
            }
            rot != orig
        }
        fn dfs(x: i64, n: i64, digits: &[i32], map: &std::collections::HashMap<i32,i32>) -> i32 {
            if x > n { return 0; }
            let mut cnt = 0;
            if x != 0 && is_confusing(x, map) { cnt += 1; }
            for &d in digits {
                if x == 0 && d == 0 { continue; }
                let nx = x * 10 + d as i64;
                if nx > n { break; }
                cnt += dfs(nx, n, digits, map);
            }
            cnt
        }
        dfs(0, n as i64, &digits, &map)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    confusingNumberII(n: number): number {
        const mp: Record<number, number> = {0:0, 1:1, 6:9, 8:8, 9:6};
        let ans = 0;
        function isConfusing(x: number): boolean {
            let orig = x, rot = 0;
            while (x > 0) {
                rot = rot * 10 + mp[x % 10];
                x = Math.floor(x / 10);
            }
            return rot !== orig;
        }
        function dfs(x: number) {
            if (x > n) return;
            if (x !== 0 && isConfusing(x)) ans++;
            for (const d of [0, 1, 6, 8, 9]) {
                if (x === 0 && d === 0) continue;
                const nx = x * 10 + d;
                if (nx > n) break;
                dfs(nx);
            }
        }
        dfs(0);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n * 5^log n), since we generate all numbers up to n using 5 digits, and each number takes O(log n) to check if it is confusing.
  • 🧺 Space complexity: O(log n), for the recursion stack.