Confusing Number II
HardUpdated: Jul 7, 2025
Practice on:
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, and9are rotated180degrees, they become0,1,9,8, and6respectively. - When
2,3,4,5, and7are rotated180degrees, they become invalid.
Note that after rotating a number, we can ignore leading zeros.
- For example, after rotating
8000, we have0008which is considered as just8.
Given an integer n, return _the number ofconfusing numbers in the inclusive range _[1, n].
Examples
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 <= 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
- Define the valid digit mapping: 0→0, 1→1, 6→9, 8→8, 9→6.
- Use backtracking to build numbers by appending valid digits, skipping leading zeros.
- For each number, check if its rotated version is valid and different from the original.
- Count such numbers.
- Start with each valid non-zero digit and recursively build larger numbers.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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)
}
}
TypeScript
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.