Skip to main content
Talentd

Confusing Number II - Solution & Explanation

HardPremiumFree on FleetCodeMathBacktracking6 min readAsked at: Google
Practice this problem

Problem Statement

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

Confusing Number I & II: Leetcode 1056/1088 • Tony Teaches • 3,111 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Confusing Number II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Confusing Number