Confusing Number II

Confusing Number II

What is this problem about?

The Confusing Number II coding problem is a significantly more difficult version. You are given an integer n and must count how many confusing numbers exist in the range [1, n]. Since n can be as large as 10^9, you cannot iterate through every number and check if it's confusing.

Why is this asked in interviews?

Google uses this Backtracking interview pattern to test your ability to generate numbers digit-by-digit. It requires a deep understanding of recursion and how to stay within a given numerical bound n. It evaluates your ability to combine "Confusing Number" logic with a combinatorial search.

Algorithmic pattern used

This is solved using Digit-by-digit Backtracking (or DFS).

1. The valid digits are [0, 1, 6, 8, 9].
2. Start a recursion from an empty number.
3. In each step, try adding one of the valid digits to the current number.
4. If the new number is <= n, check if it's "confusing" using the logic from the previous problem.
5. Increment the count if it's confusing and recurse further.
6. Special care: The first digit cannot be 0 unless the number itself is just 0.

Example explanation

n = 20

1. Start with 1. 1 is valid. Rotated is 1. 1==1, not confusing.
   • Recurse: 10, 11, 16, 18, 19.
   • 10: Rotated 01=1. 1 != 10. Confusing! Count = 1.
   • 11: Rotated 11. Not confusing.
   • 16: Rotated 91. 91 > 20. Stop.
2. Start with 6. 6 is valid. Rotated is 9. 9 != 6. Confusing! Count = 2.
   • Recurse: 60, 61... all > 20.
3. Start with 8. Not confusing.
4. Start with 9. Rotated is 6. 6 != 9. Confusing! Count = 3. Result: 3.

Common mistakes candidates make

• Brute Force: Trying to check every number from 1 to 10^9.
• Zero as First Digit: Incorrectly starting a multi-digit number with 0 (e.g., 01, 06).
• Rotation Logic: Implementing the rotation check incorrectly within the recursion, leading to an incorrect count.

Interview preparation tip

When generating numbers digit-by-digit, always pass the current number as an integer instead of a string to save on memory and time. You can add a digit d using current * 10 + d.