Rotated Digits

Rotated Digits

What is this problem about?

The Rotated Digits interview question asks you to count how many numbers in the range [1, n] are "good." A number is good if, when each of its digits is rotated 180°, the result is a valid number that is DIFFERENT from the original. Digits that remain valid after rotation: 0→0, 1→1, 2→5, 5→2, 6→9, 8→8, 9→6. Digits that become invalid: 3, 4, 7. A number is good if all its digits rotate to valid digits AND at least one digit changes (2, 5, 6, or 9 must appear).

Why is this asked in interviews?

Uber, Arista Networks, Meta, Amazon, and Google ask this problem because it applies per-digit validation logic with a classification rule. It has a dynamic programming optimization: for larger n, digit DP can count valid numbers without checking each one individually. It evaluates candidates' ability to break a mathematical condition into per-digit classification.

Algorithmic pattern used

The simple pattern is digit-by-digit validation. For each number i in [1, n], check all digits: if any digit is in {3, 4, 7}, it's invalid. If all digits are in {0,1,2,5,6,8,9} and at least one is in {2,5,6,9} (it changes), it's good. The DP pattern: classify each digit as 0 (invalid), 1 (valid, unchanged), or 2 (valid, changes). Build prefix counts using digit DP for O(log n) time.

Example explanation

n = 10. Check 1–10:

• 1: digits={1}, all valid, none change → NOT good.
• 2: digits={2}, changes → good!
• 3: invalid digit → NOT good.
• 4: invalid → NOT good.
• 5: changes → good!
• 6: changes → good!
• 7: invalid → NOT good.
• 8: valid, doesn't change → NOT good.
• 9: changes → good!
• 10: digits 1,0 — valid, none change → NOT good.

Count: 4 (numbers 2, 5, 6, 9).

Common mistakes candidates make

• Including numbers where all digits are valid but NONE change (e.g., 0, 1, 8, 10, 11, 18) — these are not "good."
• Forgetting that 0 is valid after rotation (0→0) but doesn't contribute a change.
• Using an O(n log n) approach when O(n) string-based digit iteration per number is sufficient for small n.
• Not handling multi-digit numbers correctly — check every digit, not just the number as a whole.

Interview preparation tip

For the Rotated Digits coding problem, the math and dynamic programming interview pattern applies for larger inputs. For the interview, the simple O(n log n) digit-check per number is usually acceptable given n ≤ 10,000. Know the classification: {3,4,7} = invalid, {0,1,8} = valid/unchanged, {2,5,6,9} = valid/changed. Google interviewers may ask for the digit DP approach for larger n — be ready to outline the DP state.