182. Happy Number
Take a positive integer n and apply one step: replace it with the sum of the squares of its decimal digits. Repeat the step on each new value.
For some starting numbers this process eventually lands on 1 and stays there — those numbers are called happy. Every other starting number ends up trapped in a repeating loop that never contains 1.
Your function receives the integer n and returns true if n is happy and false otherwise.
For example, starting from 19: 1² + 9² = 82, then 8² + 2² = 68, then 6² + 8² = 100, then 1² + 0² + 0² = 1 — so 19 is happy.
Example 1:
Input: n = 19
Output: true
Explanation: 19 → 82 → 68 → 100 → 1. The chain reaches 1, so 19 is happy.
Example 2:
Input: n = 2
Output: false
Explanation: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … the value 4 repeats, so the chain cycles forever without touching 1.
Constraints:
- 1 ≤ n ≤ 2³¹ - 1
Hints:
Simulate the digit-square step directly. The only danger is running forever — the chain either hits 1 or revisits a value it has already produced. What structure tells you in O(1) whether you've seen a value before?
Notice the chain is exactly like following `next` pointers in a linked list: it either terminates (reaches 1) or enters a cycle. Floyd's slow/fast pointer trick detects the cycle with no extra memory — advance one value a single step and another value two steps until they meet.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 19
Expected output: true