Confusing Number II

Confusing Number II is a classic backtracking-by-construction problem. Instead of testing every number up to N, we only ever build numbers out of the digits that can possibly matter — a huge pruning win.

The slow way first

The obvious idea: loop x from 1 to N, rotate each x, and count the ones whose rotation is valid and different. That is O(N · digits) — fine for small N, but N can be up to a billion, so a full scan is hopeless.

The question to ask: most numbers can never be confusing — why visit them at all? Any number containing a 2, 3, 4, 5, or 7 is instantly disqualified. So rather than filtering after the fact, we should only ever construct numbers made of {0, 1, 6, 8, 9}.

The idea: build numbers from valid digits only

Run a DFS that grows a number one digit at a time. Start from 0, and at each step append one of the five rotatable digits, forming cur * 10 + d. The moment cur exceeds N, that whole branch is dead — prune it. For every number we build, rotate it; if the rotation differs from the original, it is confusing and we count it.

Because we never form a number with a bad digit, the search tree is tiny: at most five children per node, and bounded by the number of digits in N. We test only candidates that have a chance of being confusing.

Walk through it

Step through the animation with N = 20. The digit cells fill left to right as DFS builds a number. We try 1, see its rotation 1 is the same (not confusing), then extend it: 16 → 91, 18 → 81, 19 → 61 are all confusing. Whenever a number passes 20, the branch is pruned and we backtrack. The running count climbs as confusing numbers are found.

Pseudocode

ROT = {0:0, 1:1, 6:9, 8:8, 9:6}   # digit -> its 180-degree image
 
dfs(cur):
    if cur > N: return 0          # prune: too big
    found = 1 if rotate(cur) != cur else 0
    for d in {0,1,6,8,9}:
        if cur == 0 and d == 0: skip   # avoid a leading-zero loop
        found += dfs(cur * 10 + d)
    return found
 
answer = dfs(0)                   # subtract the 0 case, which is never in [1, N]

The Python solution

ROT = {0:0, 1:1, 6:9, 8:8, 9:6}
 
def confusing_number_ii(n):
    def dfs(cur):
        if cur > n:
            return 0
        found = 1 if is_confusing(cur) else 0
        for d in ROT:
            if cur == 0 and d == 0:
                continue
            found += dfs(cur * 10 + d)
        return found
    return dfs(0) - (1 if is_confusing(0) else 0)

• ROT maps each rotatable digit to the digit it becomes after a 180° flip.
• dfs(cur) explores the number built so far. The very first check, cur > n, prunes any branch that has already grown past N.
• is_confusing(cur) rotates cur (flip each digit via ROT, reverse the order) and returns True only when the result differs from cur. We add 1 for each confusing number.
• The loop appends every valid next digit. The cur == 0 and d == 0 guard skips a pure leading zero, which would otherwise loop forever on 0 → 0 → 0.
• We start from dfs(0) and subtract the 0 case at the end, since 0 is not in the range [1, N].

Complexity

Here D is the number of digits in N (at most 10 for a billion). Instead of touching all N numbers, we build only those made of five digits, so the work depends on the digit length, not the magnitude of N. The space is the recursion depth, O(D).

When this pattern shows up

Practice