Find numbers that rotate 180 degrees into a different valid number
Filed under Google
Free read 2 of 3Confirm whether rotating the whole number also reverses digit order (physical rotation) or digits are mapped in place, and the range size. The example 1..10 gives 6 and 9 under the physical reading, where 10 becomes the invalid '01'.
The question
Given integers lo and hi, return every n in [lo, hi] that is valid yet different after a 180-degree rotation: 0, 1, 8 stay the same, 6 and 9 swap, any other digit makes n invalid, the rotated number must not start with 0, and it must differ from n.
Constraints
- 1 <= lo <= hi <= 10^6 (assumed)
- Digits 2, 3, 4, 5 and 7 make a number invalid
Examples
- Input
- lo = 1, hi = 10
- Output
- [6, 9]
- Why
- 6 rotates to 9 and 9 to 6; 1 and 8 rotate to themselves; 10 rotates to '01' which has a leading zero.
- Input
- lo = 11, hi = 20
- Output
- [16, 18, 19]
- Why
- 16 -> 91, 18 -> 81, 19 -> 61 are valid and different; 11 is unchanged and 20 contains an invalid digit.
Approach
Confirm whether rotating the whole number also reverses digit order (physical rotation) or digits are mapped in place, and the range size. The example 1..10 gives 6 and 9 under the physical reading, where 10 becomes the invalid '01'.
Loop over the range, build the rotated string, and compare. This is O(N * d) for N numbers of d digits and is fine for small ranges.
For huge ranges, generate only numbers made of digits {0,1,6,8,9} by DFS and count or filter those within [lo, hi], pruning when the prefix exceeds hi. The search space is 5^d instead of 10^d.
Single digits, numbers ending in 0 (rotation starts with 0, invalid), self-rotating numbers like 69, 88 and 11 (excluded as equal), and lo greater than 1 or equal to hi.
Solution
O(N * d) time for N numbers in range with d digits, O(1) extra space
def rotated_different(lo, hi):
flip = {'0': '0', '1': '1', '8': '8', '6': '9', '9': '6'}
out = []
for n in range(max(lo, 1), hi + 1):
s = str(n)
if all(c in flip for c in s):
r = ''.join(flip[c] for c in reversed(s)) # rotate whole number
if r[0] != '0' and r != s: # no leading zero, must differ
out.append(n)
return out
Tips
- What they are testing: Digit-wise validation logic and careful reading of the rules (invalid digits, leading zero, must differ), plus whether you can scale beyond a plain loop.
- Common mistake: Forgetting to exclude numbers whose rotation equals the original (11, 69, 88) or ignoring the reversal of digit order when the whole number is rotated.
Related Google questions
Collected from public candidate posts and coding forums. Updated Nov 2026.