#202
Happy Number
Easy HashSet cycle detection
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Replace a number by the sum of the squares of its digits, again and again. It's "happy" if this reaches 1; otherwise it loops forever. Decide which.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does "sum of squared digits" reach 1, or loop forever?
Why this works: a repeated number means a loop; a set detects it.
Example: 19
1+81 = 82 → 64+4 = 68 → 36+64 = 100 → 1 ✓ happy✦Hints open one at a time
If you see a number twice, you're in a loop.
Store seen numbers in a HashSet (or use slow/fast pointers).
↗Approach
Keep computing the next value until it's 1 (happy) or already in the set (loop).
</>Solution (Java)
import java.util.*;
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && seen.add(n)) { // add fails on a repeat
int next = 0;
while (n > 0) {
int d = n % 10;
next += d * d;
n /= 10;
}
n = next;
}
return n == 1;
}
}!Common mistake
Looping without detecting repeats — the program never ends for unhappy numbers.
Complexity
- Time: O(log n) per step; the sequence quickly drops below a few hundred.
- Space: O(log n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon