Happy Number
Easy · Two Pointers · Hash Table · Math · Two Pointers
Problem
Take a positive integer n and repeatedly replace it with the sum of the squares of its decimal digits. If this process eventually reaches 1, the number is called *happy*. If it instead falls into a loop that never contains 1, it is not happy.
Return True if n is happy and False otherwise.
Examples
Input: n = 7 Output: true
7 → 49 → 97 → 130 → 10 → 1, so 7 is happy.
Input: n = 4 Output: false
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 loops without reaching 1.
Input: n = 100 Output: true
1² + 0² + 0² = 1 after a single step.
Constraints
- 1 <= n <= 2^31 - 1
Approaches
- Remember every value in a set — time O(log n), space O(log n)
Follow-up
Every sequence here ends in one of two loops: the fixed point 1, or the 8-value loop through 4. Knowing that, you could stop as soon as you hit 4, but that uses a fact you would have to prove; Floyd’s method needs no such knowledge and works for any function whose values stay bounded.
Related problems
Start free on Cariara · Coding problems · System design studio
