Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Confusing Number II solution and explanation

HardBacktrackingMath4 min read47.1% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atGoogle
Practise Confusing Number II
15:41
Confusing Number I & II: Leetcode 1056/1088Tony Teaches · 15:41 · 3K viewsWatch on YouTube
6 more videos on this problem
  1. Confusing Number I & II: Leetcode 1056/1088Tony Teaches · 15:41 · 3K views
  2. 米开：LeetCode 1088. Confusing Number IIM.C米开朗基罗 · 8:42 · 1K views
  3. 1088. Confusing Number II | English | HardSimple Code - 단순코드 · 10:15 · 1K views
  4. 1088. Confusing Number II - Week 4/5 Leetcode January ChallengeProgramming Live with Larry · 29:33 · 442 views
  5. Confusing Number II - LeetCode PremiumLeetCode Україна · 16:35 · 75 views
  6. LeetCode 1088: Confusing Number IIAlitaCode · 28:38 · 6 views
  7. LeetCode 1088: Confusing Number IIAlitaCode · 28:46 · 5 views

The 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 of confusing numbers in the inclusive range [1, n].

Example 1:

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:

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 <= 109

Approach overview

Problem Overview: Given an integer n, count how many numbers in the range [1, n] become a different valid number after rotating each digit 180 degrees. Only digits 0,1,6,8,9 remain valid after rotation. The rotated number must be different from the original.

Approach 1: Brute Force Rotation Check (O(n log n) time, O(1) space)

Iterate through every number from 1 to n. For each value, build its rotated form using the mapping {0→0, 1→1, 6→9, 8→8, 9→6}. If any digit is outside this set, the number is invalid after rotation. Otherwise construct the rotated number digit by digit and compare it with the original. If the rotated value is different, it is a confusing number and contributes to the count. This method is straightforward but inefficient for large n because every number must be checked.

Approach 2: Backtracking Digit Generation (O(5^d) time, O(d) space)

Instead of scanning every number, generate only numbers composed of valid digits using backtracking. Start from an empty number and append digits from the valid set {0,1,6,8,9}. During generation, stop exploring when the current value exceeds n. For each constructed number, compute its rotated value by reversing digits and applying the rotation mapping. If the rotated result differs from the original, count it as confusing.

The key insight: most numbers contain invalid digits. Generating only valid-digit combinations drastically reduces the search space. The recursion depth equals the number of digits in n, and each step tries five possibilities. Rotation checking is constant per generated number.

This technique combines digit generation with pruning, a common pattern in math and combinatorial search problems. The DFS tree explores candidates like 1, 6, 9, 10, 11, 16... but immediately stops when a prefix already exceeds n.

Recommended for interviews: The backtracking approach. Brute force demonstrates understanding of the rotation rule, but the optimized generation method shows you can reduce the search space using DFS and digit constraints. Interviewers expect pruning logic and correct rotation validation.

Solution

class Solution:
    def confusingNumberII(self, n: int) -> int:
        def check(x: int) -> bool:
            y, t = 0, x
            while t:
                t, v = divmod(t, 10)
                y = y * 10 + d[v]
            return x != y

        def dfs(pos: int, limit: bool, x: int) -> int:
            if pos >= len(s):
                return int(check(x))
            up = int(s[pos]) if limit else 9
            ans = 0
            for i in range(up + 1):
                if d[i] != -1:
                    ans += dfs(pos + 1, limit and i == up, x * 10 + i)
            return ans

        d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
        s = str(n)
        return dfs(0, True, 0)
class Solution {
    private final int[] d = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
    private String s;

    public int confusingNumberII(int n) {
        s = String.valueOf(n);
        return dfs(0, 1, 0);
    }

    private int dfs(int pos, int limit, int x) {
        if (pos >= s.length()) {
            return check(x) ? 1 : 0;
        }
        int up = limit == 1 ? s.charAt(pos) - '0' : 9;
        int ans = 0;
        for (int i = 0; i <= up; ++i) {
            if (d[i] != -1) {
                ans += dfs(pos + 1, limit == 1 && i == up ? 1 : 0, x * 10 + i);
            }
        }
        return ans;
    }

    private boolean check(int x) {
        int y = 0;
        for (int t = x; t > 0; t /= 10) {
            int v = t % 10;
            y = y * 10 + d[v];
        }
        return x != y;
    }
}
class Solution {
public:
    int confusingNumberII(int n) {
        string s = to_string(n);
        int d[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        auto check = [&](int x) -> bool {
            int y = 0;
            for (int t = x; t; t /= 10) {
                int v = t % 10;
                y = y * 10 + d[v];
            }
            return x != y;
        };
        function<int(int, int, int)> dfs = [&](int pos, int limit, int x) -> int {
            if (pos >= s.size()) {
                return check(x);
            }
            int up = limit ? s[pos] - '0' : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (d[i] != -1) {
                    ans += dfs(pos + 1, limit && i == up, x * 10 + i);
                }
            }
            return ans;
        };
        return dfs(0, 1, 0);
    }
};
function confusingNumberII(n: number): number {
    const s = n.toString();
    const d: number[] = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
    const check = (x: number) => {
        let y = 0;
        for (let t = x; t > 0; t = Math.floor(t / 10)) {
            const v = t % 10;
            y = y * 10 + d[v];
        }
        return x !== y;
    };
    const dfs = (pos: number, limit: boolean, x: number): number => {
        if (pos >= s.length) {
            return check(x) ? 1 : 0;
        }
        const up = limit ? parseInt(s[pos]) : 9;
        let ans = 0;
        for (let i = 0; i <= up; ++i) {
            if (d[i] !== -1) {
                ans += dfs(pos + 1, limit && i === up, x * 10 + i);
            }
        }
        return ans;
    };
    return dfs(0, true, 0);
}
func confusingNumberII(n int) int {
	d := [10]int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
	s := strconv.Itoa(n)
	check := func(x int) bool {
		y := 0
		for t := x; t > 0; t /= 10 {
			v := t % 10
			y = y*10 + d[v]
		}
		return x != y
	}
	var dfs func(pos int, limit bool, x int) int
	dfs = func(pos int, limit bool, x int) (ans int) {
		if pos >= len(s) {
			if check(x) {
				return 1
			}
			return 0
		}
		up := 9
		if limit {
			up = int(s[pos] - '0')
		}
		for i := 0; i <= up; i++ {
			if d[i] != -1 {
				ans += dfs(pos+1, limit && i == up, x*10+i)
			}
		}
		return
	}
	return dfs(0, true, 0)
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force Rotation CheckO(n log n)O(1)Simple baseline approach when n is small or when demonstrating the rotation logic first
Backtracking Digit GenerationO(5^d)O(d)Optimal approach for large n; generates only valid-digit numbers and prunes branches exceeding n

Frequently asked questions

Is Confusing Number II easy or hard?

Confusing Number II is classified as Hard because it combines digit transformation with search space pruning. The challenge is recognizing that generating valid numbers via backtracking is much more efficient than checking every number up to n.

Confusing Number II Python/Java solution

Python and Java solutions typically implement DFS that builds numbers using valid digits and checks rotation with a mapping table. The algorithm prunes when the current value exceeds n and increments the count when the rotated number differs from the original.

How to solve Confusing Number II in O(n)?

A strict O(n) solution is not typically used. The common method generates only valid numbers using backtracking, which is closer to O(5^d). This is more efficient than checking all numbers up to n because many numbers contain invalid digits.

What is the best approach for Confusing Number II?

Backtracking with digit generation is the most efficient approach. Generate numbers using only valid digits (0,1,6,8,9), prune when the number exceeds n, and compute the rotated value to check if it differs from the original. This avoids scanning all numbers up to n and reduces the search space significantly.

Is Confusing Number II asked at Google/Amazon/Meta?

Confusing Number variants frequently appear in interviews at companies like Google and Amazon. The problem tests digit manipulation, DFS generation, and pruning strategies, which are common in system design and algorithm interviews.

What data structure is used in Confusing Number II?

The main technique is DFS/backtracking with recursion. A small hash map or dictionary stores the digit rotation mapping (0→0, 1→1, 6→9, 8→8, 9→6) used to construct the rotated number.

What is the time complexity of Confusing Number II?

The optimal backtracking solution runs in O(5^d) time where d is the number of digits in n. Each digit position can choose from five valid digits. Space complexity is O(d) due to recursion depth during DFS generation.

Comments

Next problem · similarConfusing NumberEasy
Now write it yourselfClose this page and solve Confusing Number II in the editor, without looking.
Practise Confusing Number II