Detect a happy number with constant memory
Define a process: replace a positive integer by the sum of the squares of its digits, and repeat. A number is happy if this process eventually reaches ; otherwise it falls into a loop that never contains .
19 -> 82 -> 68 -> 100 -> 1 happy
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ... loops, not happy
Decide whether n is happy in extra space. A visited-set works but costs memory, the interviewer wants the constant-space version.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.