Problem statement
Given a positive integer n, count the confusing numbers in the inclusive range [1,n].
A number is confusing when turning it upside down by 180 degrees gives a different number, with every digit still valid. Only 0, 1, 6, 8 and 9 survive this rotation. The other digits cannot be used.
For example, 16 turns into 91. Both digits remain valid and the value changes, so 16 counts. But 69 turns back into 69, so it does not count.
Leading zeros after rotation are ignored: 8000 turns into 0008, which means 8. The rotated number does not have to lie in [1,n]; the range applies to the original number. For n=20, 16 counts even though its rotation, 91, exceeds 20.
The official LeetCode problem is 1088. Confusing Number II, not 504. Its statement is Premium. We use your supplied problem definition and code here, without inventing numeric constraints hidden on the public page. The implementation accepts a positive Java int; candidate and rotated values use long.
Constraints & requirements
- CONTRACT
- The supplied method accepts a positive Java int n. Generate only 0,1,6,8,9, forbid a leading zero, and exclude unchanged rotations. Use long for generated and rotated values. LeetCode lists this as problem 1088, Premium; no numeric bound hidden behind its paywall is claimed here.
Examples 3 test cases
Example 1 Case 1
- Input
n=20- Output
6
The six numbers are 6,9,10,16,18,19; their rotations are 9,6,1,91,81,61.
Example 2 Case 2
- Input
n=100- Output
19
Count valid changed rotations, including 100→1, but exclude unchanged numbers such as 69,88,96.
Example 3 Case 3
- Input
n=1- Output
0
1 rotates into itself, and 0 is outside the requested range.
Hints Optional
01Hint 1
Build candidates with the five valid digits instead of scanning every integer.
02Hint 2
Rotation reads from right to left as well as mapping 6↔9. Valid digits alone do not imply a changed number.
03Hint 3
Each call counts its own number and adds all child counts. Keep extending unchanged numbers; skip only the root zero and candidates above n.
How to think before coding
A call returns the count for its positive current number AND all allowed descendants. Initialize its own contribution from the rotation test, then add child counts. An unchanged number can still have confusing children, so it is not a stopping condition. Only skip the root zero and an appended candidate above n. Construct in long before the comparison, and do not require the rotated value itself to fit the requested range.
Brute force and the improvement
A simple brute-force solution scans 1 through n and rotates each number, rejecting an invalid digit immediately. This is correct, but it spends time visiting numbers we already know cannot qualify.
Instead, grow candidates using only the five valid digits. From 1, append 0, 1, 6, 8 or 9 to produce 10, 11, 16, 18 and 19. From 6, produce 60, 61, 66, 68 and 69. If a candidate exceeds n, do not recurse into it.
This is DFS over a tree of decimal prefixes, not DFS over a graph. Each recursive call decides which valid digit to append next.
Why start at zero but never count zero?
Zero represents an empty construction root. Appending a nonzero digit starts a real number: 0 * 10 + 6 = 6.
Appending zero to that root produces zero again. If we recursed into it, we would keep calling dfs(0,n) forever. The next == 0 guard stops that cycle and prevents leading-zero representations such as 01 from duplicating 1.
Zero is still allowed inside a positive number. From 1, appending zero gives 10, which is a valid candidate.
Why continue from a number that is not confusing?
Because its children can be confusing. The number 1 is unchanged, but 10, 16, 18 and 19 all change after rotation.
“Do not count this number” is different from “do not explore this prefix.” Likewise, a confusing prefix does not guarantee confusing children: 6 counts, but its child 69 does not.
Intuition: valid digits first, changed value second
There are two separate questions:
- Can every digit survive rotation?
- Is the rotated number different from the original?
Passing only the first test is not enough.
| Original digit | After rotation | Allowed? |
|---|---|---|
| 0 | 0 | Yes |
| 1 | 1 | Yes |
| 6 | 9 | Yes |
| 8 | 8 | Yes |
| 9 | 6 | Yes |
| 2, 3, 4, 5, 7 | Invalid | No |
Rotation also reverses the positions
Imagine rotating a card showing 16. The right-hand 6 moves to the left and becomes 9. The left-hand 1 moves to the right and remains 1. The result is 91, not 19.
We can reproduce that operation by reading the original digits from right to left, mapping each digit, and appending it to a new number.
| Number | Rotation | Classification |
|---|---|---|
| 6 | 9 | Valid and different: count it |
| 10 | 01 → 1 | Valid and different: count it |
| 16 | 91 | Valid and different: count it |
| 69 | 69 | Valid but unchanged: do not count |
| 88 | 88 | Valid but unchanged: do not count |
| 25 | Invalid digits | Cannot be a confusing number |
Algorithm
- Store the valid digit-to-rotated-digit mapping.
- Start
dfs(0,n)with no positive digits chosen. - In each call, start a local count at 1 only if
currentis positive and confusing; otherwise start at 0. - Try every valid digit. Form
next = current * 10 + digit. - Skip
next == 0andnext > n. - Recurse for every remaining child and add the returned count.
- Return the total for the current number and all of its descendants.
To check a candidate, save its original value, repeatedly extract its last digit, append the mapped digit to rotated, and remove the digit just read. Return whether rotated != original.
Java solution
The map-based DFS counts each current number and adds its descendants. The public instance method remains confusingNumberII(int n); the complete main method runs all three examples.
import java.util.*;
class Solution {
// The key is the original digit; the value is its 180-degree rotation.
private static final Map<Integer, Integer> ROTATION = Map.of(
0, 0, 1, 1, 6, 9, 8, 8, 9, 6
);
public int confusingNumberII(int n) {
return dfs(0, n); // Zero is a construction root, not an answer in [1,n].
}
private int dfs(long current, int n) {
// Count THIS number only if it is positive and its rotated value differs.
int count = current != 0 && isConfusing(current) ? 1 : 0;
for (int digit : ROTATION.keySet()) { // Map iteration order is unspecified; all keys are tried.
long next = current * 10 + digit; // Append one valid digit; long avoids int overflow.
if (next == 0) continue; // Root 0→0 would repeat forever and create leading-zero paths.
if (next > n) continue; // Every extension would be even larger; prune this branch.
count += dfs(next, n); // Add each child's count, not just its confusing/not-confusing flag.
}
return count; // Includes current and ALL permitted descendant numbers.
}
private boolean isConfusing(long num) {
long original = num; // Remember it before consuming its digits.
long rotated = 0; // Numeric construction automatically ignores leading zeros.
while (num > 0) {
int digit = (int) (num % 10); // Read the rightmost digit: rotation reverses positions.
rotated = rotated * 10 + ROTATION.get(digit); // Map the digit and append it.
num /= 10; // Remove the digit just processed.
}
return rotated != original; // Valid digits are insufficient: 69 rotates back into 69.
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.confusingNumberII(20)); // 6
System.out.println(solution.confusingNumberII(100)); // 19
System.out.println(solution.confusingNumberII(1)); // 0
}
}The invocation prints 6, 19 and 0, on separate lines. isConfusing is private and receives only valid-digit candidates generated by DFS. It is not a general-purpose validator for arbitrary integers: looking up an invalid digit such as 2 would return no mapping.
Why use long if n is an int?
We compute current * 10 + digit before comparing it with n. A candidate beyond the bound can overflow an int before the guard gets a chance to reject it.
The rotated value can also exceed the original. For example, 1,000,000,006 rotates to 9,000,000,001. That original fits in an int, but its rotation does not. Using long for both constructions protects these operations for positive int inputs. The answer itself is a count of a subset of [1,n], so it cannot exceed n.
Why use continue, not break?
Your code iterates over ROTATION.keySet(). The Java Map contract does not guarantee an ascending iteration order for maps created with Map.of.
If one digit produces a value above n, a later digit might still fit. continue rejects only that child. A break would be safe only with an explicitly ascending digit sequence. The count does not depend on which sibling is visited first.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: n = 20
What to track: Track current, each call’s count, and rotated inside isConfusing. Child digits are grouped in ascending order for reading; Map.keySet does not promise that runtime order.
-
Use zero only as the construction root
Java operationif (next == 0) continue;Stateroot current = 0; count = 0; appending digit 0 is skippedThis prevents a 0→0 recursive loop and forbids leading-zero paths. Root zero is not counted.
-
Explore an unchanged prefix anyway
Java operationint count = current != 0 && isConfusing(current) ? 1 : 0;Statechild current = 1; rotated = 1; this call’s own count starts at 01 is not confusing, but its longer descendants can be. The code does not return just because this number is unchanged.
-
Count 10 and prune its extensions
Java operationcount += dfs(next, n);Statecurrent = 10 rotates to 1, so its own count = 1; all next values 100,101,106,108,109 exceed 20; return 1The parent for current = 1 adds this child’s entire count. Leading zero after rotation is ignored numerically.
-
Do not count 11
Java operationreturn rotated != original;Statecurrent = 11; rotated = 11; child count = 0; extensions exceed 20Valid digits alone are insufficient: the rotated integer must differ.
-
Trace the rotation of 16
Java operationrotated = rotated * 10 + ROTATION.get(digit);Statenum 16: digit 6 gives rotated 9; num becomes 1; digit 1 gives rotated 91; num becomes 0Reading digits right to left reverses their positions as well as mapping 6↔9. 91 may exceed n; only the original candidate is bounded.
-
Finish the 1-prefix subtree
Java operationcount += dfs(next, n);State16,18,19 each return 1; current-1 count = 1 + 0 + 1 + 1 + 1 = 4Each of these two-digit nodes has no extension ≤20. The current-1 frame returns the sum of its child counts.
-
Finish the root’s other children
Java operationcount += dfs(next, n);Statecurrent 6 returns 1, current 8 returns 0, current 9 returns 1; root total = 4+1+0+16 and 9 change under rotation, whereas 8 does not. Their extensions all exceed 20, so the root returns 6.
Final result: 6, from 10,16,18,19 in the 1-prefix subtree plus 6 and 9.
For n=20, here are all recursive calls, grouped in ascending digit order to make the tree readable. This grouping is not a promise about the map’s runtime iteration order. Rejected candidates do not become recursive calls.
dfs(0,20) own count = 0 ├─ digit 0: next=0 → skip no child call ├─ dfs(1,20) 1→1, own count = 0 │ ├─ dfs(10,20) → 10→1 return 1 │ ├─ dfs(11,20) → 11→11 return 0 │ ├─ dfs(16,20) → 16→91 return 1 │ ├─ dfs(18,20) → 18→81 return 1 │ └─ dfs(19,20) → 19→61 return 1 │ every child above is at least 10; │ its extensions are >=100 >20 → no deeper calls │ return 0 + 1 + 0 + 1 + 1 + 1 = 4 ├─ dfs(6,20) → 6→9 own count = 1 │ next candidates 60,61,66,68,69 >20 → skip; return 1 ├─ dfs(8,20) → 8→8 own count = 0 │ next candidates 80,81,86,88,89 >20 → skip; return 0 └─ dfs(9,20) → 9→6 own count = 1 next candidates 90,91,96,98,99 >20 → skip; return 1 root returns 0 + 4 + 1 + 0 + 1 = 6 counted numbers: [6,9,10,16,18,19]
There are ten calls in total, including the artificial root. We count a number at its node, not only at leaves. For a larger bound, 6 would still count even when it has eligible descendants.
Follow the rotation of 16
| Moment | Remaining num | Digit read | Mapped digit | Rotated so far |
|---|---|---|---|---|
| Start | 16 | — | — | 0 |
| First iteration | 16 | 6 | 9 | 0*10+9 = 9 |
| Remove the digit | 1 | — | — | 9 |
| Second iteration | 1 | 1 | 1 | 9*10+1 = 91 |
| Remove the digit | 0 | — | — | 91 |
Now the loop ends. The saved original is 16; 91 != 16, so the call contributes one. original is needed because num has been consumed down to zero.
For 10, the first mapped digit is 0, so the accumulator stays zero. The next mapped digit is 1, so it becomes 1. Numeric construction naturally discards leading zeros; there is no separate string-trimming step.
What is in the actual call stack?
While checking 16 on this branch, the active stack is:
TOP isConfusing(16) original=16; num being consumed; rotated being built
dfs(16,20) waiting for the rotation result
dfs(1,20) waiting for this child's returned count
BOTTOM dfs(0,20) waiting for the complete 1-prefix branchAfter isConfusing returns true, dfs(16,20) sets its own count to 1. All its proposed extensions exceed 20, so it returns 1 and its frame leaves the stack. dfs(1,20) adds that returned value and continues to another child.
The tree shows all calls across time; the stack shows only calls still active at one moment. Sibling calls such as dfs(10,20) and dfs(16,20) are not simultaneously on the stack.
Why is there no explicit undo?
current, next and count are primitive values local to each call. Calling a child does not overwrite the parent’s current value. There is no shared path list, visited set or mutable digit buffer to restore.
The search still tries alternatives and returns to its parent, but it does not need a remove or current /= 10 after the child. That differs from N-Queens, where shared column and diagonal reservations must be removed.
Why it works
Validity: every generated digit comes from the rotation map. The root-zero guard ensures a positive candidate has no leading zero. The bound guard allows a call only when its original value is at most n. The rotation check counts it only if its value changes.
Completeness: take any qualifying number in [1,n]. Its first digit is one of 1,6,8,9 and its remaining digits come from 0,1,6,8,9. DFS tries that exact sequence. Every positive prefix is at most the complete number, so none of its prefixes is pruned above n.
No duplicates: a positive integer has one ordinary decimal representation without leading zeros. That representation gives exactly one path of appended digits. No other path generates the same integer.
Correct count: a call contributes either zero or one for its own number, plus the counts from disjoint child subtrees. The root contributes zero. Adding all these contributions counts each confusing number once, and no unchanged number.
Termination: zero cannot recurse into zero. Every later child of a positive current number is strictly larger and has one more digit. Eventually its value exceeds n, so the branch stops.
Complexity and alternative approaches
Let d be the number of decimal digits in n and G be the number of positive valid-digit candidates actually visited.
Each candidate takes at most O(d) work to rotate, plus a constant five attempted children. Your solution therefore takes O(G·d) time. Pruning changes G, but does not remove the digit-by-digit rotation cost.
There are 4*5^(length−1) valid-digit numbers of a fixed positive length: four choices for the first digit and five for every later digit. Across all lengths up to d, there are at most 5^d−1 candidates, before restricting them to n. A convenient upper bound is O(d·5^d). This is exponential in the number of digits, not O(d) and not O(1).
Auxiliary space is O(d) for recursive frames. The rotation map has five entries and the helper uses a fixed number of variables. There is no output list; returning one count does not make the recursive stack constant-space.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Scan all integers, validate and rotate | O(n·d) | O(1) | Simple but visits invalid-digit numbers too |
| Your valid-digit DFS, then rotate | O(G·d) | O(d) | Avoids impossible digits; easiest generation version to explain |
| Carry the rotated value while extending | O(G) | O(d) | Avoids rescanning digits; needs an extra place-value invariant |
For the third approach, if the old number has k digits and you append digit x, update nextRotation = rotation(x) * 10^k + oldRotation. The newly appended digit becomes the first digit after rotation. For example, extending 16 by 0 gives 160, whose rotation is 0*100+91 = 91. This is a possible optimization, not the method used in the published Java above.
Another counting approach subtracts unchanged strobogrammatic candidates from all positive valid-digit candidates within the bound. It can use digit counting to avoid enumeration, but the upper-bound handling is more involved. Start with the verified DFS before introducing that optimization.
Common mistakes
- Counting every number containing only valid digits. That wrongly includes 1,8,11,69,88 and 96.
- Mapping digits without reversing their positions. That turns 16 into 19 instead of 91.
- Recursing from root zero back to zero, causing infinite recursion.
- Forbidding zero everywhere and losing answers such as 10 or 100.
- Stopping because the current number is unchanged, losing confusing descendants.
- Counting only leaves and missing eligible shorter numbers.
- Requiring the rotated value to be at most n. Only the original is range-bound.
- Using
breakwith an unordered map, which can skip smaller eligible siblings. - Using int intermediates and overflowing before the bound check.
- Sharing a mutable total between calls instead of returning local subtree counts, which can make repeated invocations accumulate old results.
Revision checks: n=6 → 1, n=9 → 2, n=10 → 3, n=11 → 3, and n=20 → 6. Passing from 10 to 11 must not increase the answer because 11 is unchanged.