Confusing Number II
Problem
A confusing number is a number that, when each digit is rotated 180 degrees, becomes a different valid number. Each digit must individually map to a valid digit when rotated: 0→0, 1→1, 6→9, 8→8, 9→6; the digits 2, 3, 4, 5, 7 are invalid. Given an integer n, return the count of confusing numbers in the range [1, n].
n = 206def confusing_number_ii(n):
rot = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
digits = [0, 1, 6, 8, 9]
count = 0
def is_confusing(x):
r, t = 0, x
while t:
r = r * 10 + rot[t % 10]
t //= 10
return r != x
def dfs(cur):
nonlocal count
if cur > n:
return
if cur != 0 and is_confusing(cur):
count += 1
for d in digits:
if cur == 0 and d == 0:
continue
dfs(cur * 10 + d)
dfs(0)
return countfunction confusingNumberII(n) {
const rot = { 0: 0, 1: 1, 6: 9, 8: 8, 9: 6 };
const digits = [0, 1, 6, 8, 9];
let count = 0;
function isConfusing(x) {
let r = 0, t = x;
while (t > 0) {
r = r * 10 + rot[t % 10];
t = Math.floor(t / 10);
}
return r !== x;
}
function dfs(cur) {
if (cur > n) return;
if (cur !== 0 && isConfusing(cur)) count++;
for (const d of digits) {
if (cur === 0 && d === 0) continue;
dfs(cur * 10 + d);
}
}
dfs(0);
return count;
}class Solution {
private int[] rot = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
private int[] digits = {0, 1, 6, 8, 9};
private long n;
private int count = 0;
public int confusingNumberII(int n) {
this.n = n;
dfs(0);
return count;
}
private boolean isConfusing(long x) {
long r = 0, t = x;
while (t > 0) {
r = r * 10 + rot[(int)(t % 10)];
t /= 10;
}
return r != x;
}
private void dfs(long cur) {
if (cur > n) return;
if (cur != 0 && isConfusing(cur)) count++;
for (int d : digits) {
if (cur == 0 && d == 0) continue;
dfs(cur * 10 + d);
}
}
}class Solution {
int rot[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
vector<int> digits = {0, 1, 6, 8, 9};
long long n;
int count = 0;
bool isConfusing(long long x) {
long long r = 0, t = x;
while (t > 0) {
r = r * 10 + rot[t % 10];
t /= 10;
}
return r != x;
}
void dfs(long long cur) {
if (cur > n) return;
if (cur != 0 && isConfusing(cur)) count++;
for (int d : digits) {
if (cur == 0 && d == 0) continue;
dfs(cur * 10 + d);
}
}
public:
int confusingNumberII(int n) {
this->n = n;
dfs(0);
return count;
}
};Explanation
A confusing number is one that turns into a different valid number when the whole thing is rotated 180 degrees. Only five digits survive rotation: 0,1,6,8,9 (with 6 and 9 swapping). So instead of checking every number up to n, we only build numbers out of those five digits.
The DFS dfs(cur) grows a number digit by digit: from cur it forms cur * 10 + d for each allowed digit d. This visits exactly the numbers made of rotatable digits and skips everything else. If cur ever exceeds n, we prune that branch since appending more digits only makes it bigger.
For each generated number we run is_confusing, which rotates it by reading digits off the end, mapping each through rot, and rebuilding the rotated value r. The number counts only if r != cur — a rotation that lands on the same number (like 1 or 88) does not count.
One guard, if cur == 0 and d == 0: continue, prevents leading zeros so we don't generate things like 00 or 06.
Example: with n = 20, the digit-building reaches 6 (rotates to 9, different → count), 9 (rotates to 6, count), 10, 16, 18, 19, all of which rotate to a different number — totaling 6 confusing numbers. A value like 11 rotates back to 11 and is rejected.