Why it works
- Each number has exactly one next number, so the numbers form a linked list, and it cannot grow forever: a number with d digits leads to at most 81·d, less than the number itself once it has four digits. So the list soon drops below a thousand, stays there and sooner or later comes back to a number it has met.
- So every list ends in a loop, and 1 is a loop too: next(1) = 1. Slow and fast meet on whatever loop it is, and the answer is just whether they meet on 1.
- No set of seen numbers is needed: the two pointers find the loop. Every number that is not happy ends in the same loop, 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.
Complexity
Time O(log n): the first step reads the digits of n, about log n of them, and gives at most 81 per digit, under a thousand for any 32-bit n; from there the path and its loop are short. Memory O(1): two numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗