Confusing Number II - Solution & Explanation

Problem Overview: Given an integer n, count how many numbers in the range [1, n] become a different valid number after rotating each digit 180 degrees. Only digits 0,1,6,8,9 remain valid after rotation. The rotated number must be different from the original.

Approach 1: Brute Force Rotation Check (O(n log n) time, O(1) space)

Iterate through every number from 1 to n. For each value, build its rotated form using the mapping {0→0, 1→1, 6→9, 8→8, 9→6}. If any digit is outside this set, the number is invalid after rotation. Otherwise construct the rotated number digit by digit and compare it with the original. If the rotated value is different, it is a confusing number and contributes to the count. This method is straightforward but inefficient for large n because every number must be checked.

Approach 2: Backtracking Digit Generation (O(5^d) time, O(d) space)

Instead of scanning every number, generate only numbers composed of valid digits using backtracking. Start from an empty number and append digits from the valid set {0,1,6,8,9}. During generation, stop exploring when the current value exceeds n. For each constructed number, compute its rotated value by reversing digits and applying the rotation mapping. If the rotated result differs from the original, count it as confusing.

The key insight: most numbers contain invalid digits. Generating only valid-digit combinations drastically reduces the search space. The recursion depth equals the number of digits in n, and each step tries five possibilities. Rotation checking is constant per generated number.

This technique combines digit generation with pruning, a common pattern in math and combinatorial search problems. The DFS tree explores candidates like 1, 6, 9, 10, 11, 16... but immediately stops when a prefix already exceeds n.

Recommended for interviews: The backtracking approach. Brute force demonstrates understanding of the rotation rule, but the optimized generation method shows you can reduce the search space using DFS and digit constraints. Interviewers expect pruning logic and correct rotation validation.