Confusing Number II

Hard Recursion & Backtracking Choice per Position Original on LeetCode

Reported atGoogle

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n log n)Each of the n numbers has O(log n) digits to inspect.
SpaceO(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.

  1. Map each digit to its rotation: 0->0, 1->1, 6->9, 8->8, 9->6, others invalid.
  2. For x from 1 to n, peel digits from the right and build the rotated value by appending rot(digit).
  3. 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;
    }
}

2Optimal (DFS over rotatable digits)

TimeO(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).
SpaceO(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.

  1. dfs(x, rotated, place) where place = 10^(digits of x).
  2. For each allowed digit d in increasing order: skip d = 0 when x = 0 (no leading zero).
  3. Let nx = x * 10 + d; if nx > n, stop trying larger digits.
  4. Let nr = rot(d) * place + rotated. If nx != nr, count it.
  5. Recurse with dfs(nx, nr, place * 10).
  6. 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);
        }
    }
}

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.