Happy Number
The key idea
Repeatedly replacing
n with the sum of the squares of its digits either reaches 1 or enters a cycle. Detecting that cycle (with a seen-set or Floyd's tortoise-and-hare) is what separates happy numbers from unhappy ones.Problem
A happy number is defined by the following process. Start with any positive integer n. Replace n by the sum of the squares of its digits. Repeat the process until n equals 1, or it loops endlessly in a cycle that never includes 1. A number is happy if this process ends at 1. Return true if n is a happy number, and false otherwise.
Constraints
- 1 <= n <= 2^31 - 1
Examples
Input: n = 19
Output: true
Input: n = 2
Output: false
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization