Confusing Number II
Confusing Number II is a hard recursion & backtracking problem solved with the choice per position pattern.
The best approach, optimal (dfs over rotatable digits), runs in O(5^D) time and O(D) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (test every number) up.
Problem
Turn a number upside down (rotate it by 180 degrees) digit by digit: 0, 1 and 8 stay as they are, 6 becomes 9 and 9 becomes 6. The digits 2, 3, 4, 5 and 7 do not give a digit when rotated, so a number containing any of them cannot be rotated at all. Leading zeros in the rotated result are dropped, so 80 rotated is 08, which is 8.
A confusing number is one that can be rotated and whose rotated value is a different number. Given n, return how many confusing numbers lie in the range [1, n].
Examples
Example 1
- Input
n = 70- Output
10- Why
- They are 6, 9, 10, 16, 18, 19, 60, 61, 66 and 68 (for example 16 turns into 91). 11 is not one: it turns into 11 again.
Example 2
- Input
n = 9- Output
2- Why
- Only 6 and 9 change; 1 and 8 stay the same and the other digits cannot be turned.
Example 3
- Input
n = 1- Output
0- Why
- 1 rotates to itself.
Constraints
1 <= n <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (test every number) | O(n log n) | O(1) |
| Optimal (DFS over rotatable digits) | O(5^D) | O(D) |
1Brute force (test every number)
O(n log n)Each of the n numbers has O(log n) digits to inspect.O(1)Only a few counters.Check each number from 1 to n on its own: rotate it digit by digit, give up on any digit that cannot be rotated, and count it when the rotated value differs from the original.
- Map each digit to its rotation: 0->0, 1->1, 6->9, 8->8, 9->6, others invalid.
- For x from 1 to n, peel digits from the right and build the rotated value by appending rot(digit).
- If every digit was valid and the rotated value differs from x, count it.
class Solution {
private static final int[] ROT = { 0, 1, -1, -1, -1, -1, 9, -1, 8, 6 };
public int confusingNumberII(int n) {
int count = 0;
for (int x = 1; x <= n; x++) {
long rotated = 0;
int rest = x;
boolean ok = true;
while (rest > 0) {
int d = rest % 10;
if (ROT[d] < 0) {
ok = false;
break;
}
rotated = rotated * 10 + ROT[d];
rest /= 10;
}
if (ok && rotated != x) count++;
}
return count;
}
}class Solution:
def confusingNumberII(self, n: int) -> int:
rot = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
count = 0
for x in range(1, n + 1):
rotated, rest, ok = 0, x, True
while rest > 0:
d = rest % 10
if rot[d] < 0:
ok = False
break
rotated = rotated * 10 + rot[d]
rest //= 10
if ok and rotated != x:
count += 1
return countclass Solution {
public:
int confusingNumberII(int n) {
const int rot[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
int count = 0;
for (int x = 1; x <= n; x++) {
long long rotated = 0;
int rest = x;
bool ok = true;
while (rest > 0) {
int d = rest % 10;
if (rot[d] < 0) {
ok = false;
break;
}
rotated = rotated * 10 + rot[d];
rest /= 10;
}
if (ok && rotated != x) count++;
if (x == INT_MAX) break;
}
return count;
}
};function confusingNumberII(n) {
const rot = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
let count = 0;
for (let x = 1; x <= n; x++) {
let rotated = 0, rest = x, ok = true;
while (rest > 0) {
const d = rest % 10;
if (rot[d] < 0) {
ok = false;
break;
}
rotated = rotated * 10 + rot[d];
rest = Math.floor(rest / 10);
}
if (ok && rotated !== x) count++;
}
return count;
}2Optimal (DFS over rotatable digits)
O(5^D)D is the number of digits of n (at most 10); every visited number uses only the 5 allowed digits and costs O(1).O(D)The recursion is at most D levels deep.Only numbers made of 0, 1, 6, 8, 9 can be confusing, and there are at most about 5^9 of them up to 10^9. Generate them with a DFS that appends one allowed digit at a time, carrying the rotated value along so it costs O(1) per number, and prune as soon as the number passes n.
- dfs(x, rotated, place) where place = 10^(digits of x).
- For each allowed digit d in increasing order: skip d = 0 when x = 0 (no leading zero).
- Let nx = x * 10 + d; if nx > n, stop trying larger digits.
- Let nr = rot(d) * place + rotated. If nx != nr, count it.
- Recurse with dfs(nx, nr, place * 10).
- Start from dfs(0, 0, 1) and return the count.
class Solution {
private static final int[] DIGITS = { 0, 1, 6, 8, 9 };
private static final int[] ROT = { 0, 1, -1, -1, -1, -1, 9, -1, 8, 6 };
private long limit;
private int count;
public int confusingNumberII(int n) {
limit = n;
count = 0;
dfs(0, 0, 1);
return count;
}
private void dfs(long x, long rotated, long place) {
for (int d : DIGITS) {
if (x == 0 && d == 0) continue;
long nx = x * 10 + d;
if (nx > limit) break;
long nr = ROT[d] * place + rotated;
if (nx != nr) count++;
dfs(nx, nr, place * 10);
}
}
}class Solution:
def confusingNumberII(self, n: int) -> int:
digits = [0, 1, 6, 8, 9]
rot = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
count = 0
def dfs(x: int, rotated: int, place: int) -> None:
nonlocal count
for d in digits:
if x == 0 and d == 0:
continue
nx = x * 10 + d
if nx > n:
break
nr = rot[d] * place + rotated
if nx != nr:
count += 1
dfs(nx, nr, place * 10)
dfs(0, 0, 1)
return countclass Solution {
const int digits[5] = {0, 1, 6, 8, 9};
const int rot[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
long long limit = 0;
int count = 0;
void dfs(long long x, long long rotated, long long place) {
for (int d : digits) {
if (x == 0 && d == 0) continue;
long long nx = x * 10 + d;
if (nx > limit) break;
long long nr = rot[d] * place + rotated;
if (nx != nr) count++;
dfs(nx, nr, place * 10);
}
}
public:
int confusingNumberII(int n) {
limit = n;
count = 0;
dfs(0, 0, 1);
return count;
}
};function confusingNumberII(n) {
const digits = [0, 1, 6, 8, 9];
const rot = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
let count = 0;
const dfs = (x, rotated, place) => {
for (const d of digits) {
if (x === 0 && d === 0) continue;
const nx = x * 10 + d;
if (nx > n) break;
const nr = rot[d] * place + rotated;
if (nx !== nr) count++;
dfs(nx, nr, place * 10);
}
};
dfs(0, 0, 1);
return count;
}Edge cases to test
- n below 6, where the answer is 0
- Numbers ending in 0 such as 10 or 60, whose rotation has a leading zero (10 becomes 01 = 1)
- Numbers that rotate to themselves (11, 69, 88, 96, 101...) must not be counted
- n = 10^9, the largest input
Hints
Hint 1
A number can only be confusing if every digit is one of 0, 1, 6, 8, 9. How many such numbers are there up to 10^9?
Hint 2
Generate exactly those numbers by appending allowed digits, stopping as soon as the value exceeds n.
Hint 3
While appending a digit d to x, the rotated value gains rot(d) as its new leading digit: rotated(x*10 + d) = rot(d) * 10^len(x) + rotated(x).
FAQ
What is the best time complexity for Confusing Number II?
Optimal (DFS over rotatable digits) runs in O(5^D) time and O(D) extra space. D is the number of digits of n (at most 10); every visited number uses only the 5 allowed digits and costs O(1).
Which pattern does Confusing Number II use?
It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Strobogrammatic Number II, Palindrome Partitioning.
Is there a brute force solution for Confusing Number II?
Yes. Brute force (test every number) takes O(n log n) time and O(1) space. Check each number from 1 to n on its own: rotate it digit by digit, give up on any digit that cannot be rotated, and count it when the rotated value differs from the original.
Which edge cases should I test for Confusing Number II?
n below 6, where the answer is 0; Numbers ending in 0 such as 10 or 60, whose rotation has a leading zero (10 becomes 01 = 1); Numbers that rotate to themselves (11, 69, 88, 96, 101...) must not be counted; n = 10^9, the largest input.