72. Happy Number
🔗 LeetCode Problem: 202. Happy Number
📊 Difficulty: Easy
🏷️ Topics: Hash Table, Math, Two Pointers
Problem Statement
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
- Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Example 1:
Input: n = 19
Output: true
Explanation:
1² + 9² = 1 + 81 = 82
8² + 2² = 64 + 4 = 68
6² + 8² = 36 + 64 = 100
1² + 0² + 0² = 1 + 0 + 0 = 1
Example 2:
Input: n = 2
Output: false
Explanation:
2² = 4
4² = 16
1² + 6² = 1 + 36 = 37
3² + 7² = 9 + 49 = 58
5² + 8² = 25 + 64 = 89
8² + 9² = 64 + 81 = 145
1² + 4² + 5² = 1 + 16 + 25 = 42
4² + 2² = 16 + 4 = 20
2² + 0² = 4 + 0 = 4
(Back to 4, cycle detected!)
Constraints:
- 1 <= n <= 2^31 - 1
🎨 Visual Understanding
The Problem Visualized
Example 1: n = 19 (Happy Number!)
19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1 ✓
Reaches 1 → Happy!
Example 2: n = 2 (Not Happy!)
2 → 2² = 4
4 → 4² = 16
16 → 1² + 6² = 37
37 → 3² + 7² = 58
58 → 5² + 8² = 89
89 → 8² + 9² = 145
145 → 1² + 4² + 5² = 42
42 → 4² + 2² = 20
20 → 2² + 0² = 4 ← Back to 4!
Cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
Never reaches 1 → Not Happy!
Visual representation of cycle:
4 ←──────────────┐
↓ │
16 20
↓ ↑
37 42
↓ ↑
58 145
↓ ↑
89 ───────────────┘
This is a CYCLE! Just like a linked list cycle!
🚨 CRITICAL INSIGHT - This is a Cycle Detection Problem!
The Key Pattern!
This problem is IDENTICAL to detecting a cycle in a linked list!
Instead of:
node.next → next node
We have:
number → sumOfSquares(number)
The "linked list":
19 → 82 → 68 → 100 → 1
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle!)
Two possible outcomes:
1. Reaches 1 (happy) ✓
2. Enters a cycle (not happy) ✗
Use Floyd's Cycle Detection!
Slow: Computes next once
Fast: Computes next twice
If they meet at 1: Happy!
If they meet elsewhere: Cycle, not happy!
Why There's Always a Cycle or Reaches 1
Mathematical insight:
For any number, the sum of squares of digits is bounded!
Largest 10-digit number: 9,999,999,999
Sum of squares: 10 × 9² = 810
So any number reduces to ≤ 3 digits quickly!
For 3-digit numbers (up to 999):
Max sum: 9² + 9² + 9² = 243
For 2-digit numbers (up to 99):
Max sum: 9² + 9² = 162
The sequence MUST eventually:
1. Reach 1 (happy) ✓
2. Enter a cycle (not happy) ✗
There are only so many numbers it can visit!
Eventually, it MUST repeat (cycle) or reach 1!
Common Cycle in Unhappy Numbers
The most common cycle for unhappy numbers:
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
Almost all unhappy numbers eventually enter this cycle!
Other possible cycles exist but are rare:
- Single digit unhappy: 2, 3, 4, 5, 6, 8, 9
- They all eventually lead to the 4-cycle!
🎯 Approach 1: Hash Set (Tracking Seen Numbers)
The Most Natural Thinking 💭
Core Logic:
Keep track of numbers we've seen
If we see a number again → cycle!
If we reach 1 → happy!
Implementation
/**
* Using HashSet to detect cycle
* Time: O(log n), Space: O(log n)
*/
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
// Calculate sum of squares of digits
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
⏰ Time: O(log n) - Number of digits reduces quickly
💾 Space: O(log n) - Store seen numbers
✓ Works well, but uses extra space!
🎯 Approach 2: Floyd's Cycle Detection (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Treat this as a linked list with cycles!
Instead of node.next, we have getNext(n)
Use fast & slow pointers:
Slow: computes next once
Fast: computes next twice
If they meet at 1: Happy!
If they meet at other number: Cycle, not happy!
The Strategy:
Floyd's Algorithm Applied:
1. Initialize slow = n, fast = n
2. Move slow one step: slow = getNext(slow)
3. Move fast two steps: fast = getNext(getNext(fast))
4. If they meet at 1 → return true
5. If they meet elsewhere → return false
Space: O(1) - No HashSet needed!
Implementation
/**
* Floyd's Cycle Detection for Happy Number
* Time: O(log n), Space: O(1)
*/
public boolean isHappy(int n) {
int slow = n;
int fast = n;
do {
slow = getNext(slow); // Move 1 step
fast = getNext(getNext(fast)); // Move 2 steps
} while (slow != fast);
// If they met at 1, it's happy!
return slow == 1;
}
// Calculate sum of squares of digits
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
⏰ Time: O(log n) - Sequence length is logarithmic
💾 Space: O(1) - Only two variables!
🔍 Dry Run
Example 1: n = 19 (Happy Number)
Goal: Check if reaches 1
Initial:
slow = 19
fast = 19
Iteration 1:
slow = getNext(19) = 1² + 9² = 82
fast = getNext(getNext(19))
= getNext(82)
= 8² + 2² = 68
= getNext(68)
= 6² + 8² = 100
slow = 82
fast = 100
slow != fast, continue
Iteration 2:
slow = getNext(82) = 8² + 2² = 68
fast = getNext(getNext(100))
= getNext(1² + 0² + 0²)
= getNext(1)
= 1² = 1
= getNext(1)
= 1² = 1
slow = 68
fast = 1
slow != fast, continue
Iteration 3:
slow = getNext(68) = 6² + 8² = 100
fast = getNext(getNext(1))
= getNext(1)
= 1
= getNext(1)
= 1
slow = 100
fast = 1
slow != fast, continue
Iteration 4:
slow = getNext(100) = 1² + 0² + 0² = 1
fast = getNext(getNext(1))
= getNext(1)
= 1
= getNext(1)
= 1
slow = 1
fast = 1
slow == fast! Loop ends
Return slow == 1? Yes! ✓
True (Happy number!)
Example 2: n = 2 (Unhappy Number)
Initial:
slow = 2
fast = 2
Iteration 1:
slow = getNext(2) = 2² = 4
fast = getNext(getNext(2))
= getNext(4)
= 4² = 16
= getNext(16)
= 1² + 6² = 37
slow = 4
fast = 37
Continue...
(Several iterations later)
Eventually:
slow enters cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
fast also in cycle, moving twice as fast
They meet at some number in the cycle (say 58)
slow = 58
fast = 58
slow == fast! Loop ends
Return slow == 1? No!
False (Not happy!)
🎯 Why This Works - Deep Dive
The Transformation as a "Linked List":
═══════════════════════════════════════════════════════════════
Think of each number as a "node":
number → getNext(number) → getNext(getNext(number)) → ...
This creates an implicit "linked list"!
Example: n = 2
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle!)
Just like: node1 → node2 → ... → node8 → node2 (cycle!)
The Two Outcomes:
═══════════════════════════════════════════════════════════════
Outcome 1: Reaches 1
19 → 82 → 68 → 100 → 1
Once at 1: getNext(1) = 1² = 1
Stays at 1 forever!
This is like a cycle of length 1 at node "1"
Both slow and fast eventually reach 1
They meet at 1 ✓
Outcome 2: Enters a cycle (not containing 1)
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
Forms a cycle that doesn't include 1
Both slow and fast enter this cycle
Fast catches slow inside the cycle
They meet at some number != 1 ✗
Floyd's Algorithm Detects Both:
═══════════════════════════════════════════════════════════════
If happy:
Both reach 1
Meet at 1
Return true ✓
If not happy:
Both enter cycle
Meet at some number != 1
Return false ✗
Why Do-While Loop?
═══════════════════════════════════════════════════════════════
do {
slow = getNext(slow);
fast = getNext(getNext(fast));
} while (slow != fast);
Why not while loop?
At start: slow = n, fast = n
They're equal!
While loop would exit immediately!
Do-while ensures:
Move first, then check
Always executes at least once ✓
Time Complexity:
═══════════════════════════════════════════════════════════════
Key insight: Sequence length is bounded!
For a d-digit number:
Next value ≤ d × 81 (since 9² = 81)
Example: 999 (3 digits)
Next: 9² + 9² + 9² = 243 (3 digits still)
The sequence converges to small numbers quickly!
Cycle length is also bounded (small)
Common cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
Length: 8
Total iterations: O(log n)
Each iteration: O(log n) to compute getNext
Overall: O(log n) ✓
Space: O(1) - Only two variables!
Why getNext Computation is O(log n)
Computing sum of squares of digits:
int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
Number of iterations = number of digits = log₁₀(n)
Example: n = 12345
5 digits → 5 iterations
log₁₀(12345) ≈ 4.09 ≈ 5 ✓
So getNext is O(log n)
⚠️ Common Mistakes to Avoid
Mistake 1: Using while instead of do-while
// ❌ WRONG - Exits immediately if slow == fast at start
while (slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
// At start, slow = n, fast = n, loop never executes!
// ✓ CORRECT - Always executes at least once
do {
slow = getNext(slow);
fast = getNext(getNext(fast));
} while (slow != fast);
Mistake 2: Checking == 1 inside loop
// ❌ INEFFICIENT - Multiple checks
do {
slow = getNext(slow);
fast = getNext(getNext(fast));
if (slow == 1 || fast == 1) {
return true;
}
} while (slow != fast);
// ✓ CORRECT - Single check after meeting
do {
slow = getNext(slow);
fast = getNext(getNext(fast));
} while (slow != fast);
return slow == 1;
Mistake 3: Wrong getNext implementation
// ❌ WRONG - Doesn't handle multiple digits correctly
private int getNext(int n) {
return n * n; // Only squares the whole number!
}
// ✓ CORRECT - Squares each digit
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
Mistake 4: Not initializing both at n
// ❌ WRONG - Different starting points
int slow = n;
int fast = getNext(n); // Fast starts ahead
// ✓ CORRECT - Both start at n
int slow = n;
int fast = n;
Mistake 5: Calling getNext with 0
// ❌ POTENTIAL ISSUE - Though it works
// getNext(0) = 0, which creates immediate cycle
// ✓ BETTER - Handle explicitly if needed
if (n == 0) return false; // 0 is not happy
🎯 Pattern Recognition
Problem Type: Cycle Detection in Transformation Sequence
Core Pattern: Fast & Slow Pointers (Floyd's Algorithm)
When to Apply:
✓ Sequence of transformations
✓ Can eventually cycle or reach target
✓ No explicit linked list structure
✓ Need O(1) space
✓ Function creates "next" relationship
Recognition Keywords:
- "Process ends in" (terminal state)
- "Loops endlessly" (cycle)
- "Replace by" (transformation)
- "Repeat the process"
- Number transformations
- Sequence of operations
Similar Problems:
- Linked List Cycle (LC 141) - Explicit linked list
- Find Duplicate Number (LC 287) - Array as linked list
- Circular Array Loop (LC 457) - Array with cycles
Key Components:
┌────────────────────────────────────────────┐
│ 1. Transformation function (getNext) │
│ 2. Two outcomes: target or cycle │
│ 3. Fast & slow pointers │
│ 4. Meet at target or in cycle │
└────────────────────────────────────────────┘
This shows Floyd's algorithm works beyond linked lists!
🧠 Interview Strategy
Step 1: "This is cycle detection, not explicit linked list"
Step 2: "Use Floyd's algorithm with transformation function"
Step 3: "If meet at 1: happy; else: cycle, not happy"
Step 4: "O(log n) time, O(1) space"
Key Points to Mention:
- Each number → next number via sum of squares
- Creates implicit "linked list"
- Two outcomes: reach 1 or enter cycle
- Use fast & slow pointers
- Do-while loop (both start at n)
- Meet at 1 → happy, else → not happy
- Time: O(log n), Space: O(1)
- Alternative: HashSet O(log n) space
Why This Approach?
"I recognize this as a cycle detection problem. Each number
transforms to the next via sum of squares of digits, creating
an implicit linked list. It either reaches 1 (happy) or enters
a cycle (not happy). I'll use Floyd's cycle detection with two
pointers moving at different speeds. When they meet, if they're
at 1, the number is happy. Otherwise, they met in a cycle."
Why Do-While?
"Since both pointers start at n, they're initially equal. A
while loop would exit immediately. The do-while ensures we
move both pointers at least once before checking if they meet."
Edge Cases to Mention:
✓ n = 1 (already happy)
✓ n = 2 (enters cycle immediately)
✓ Small numbers (quick convergence)
✓ Large numbers (rapid reduction)
📝 Quick Revision Notes
🎯 Core Concept:
Happy Number: Each number → sum of squares of digits. Reaches 1 (happy ✓) or enters cycle (not happy ✗). Use Floyd's algorithm! Slow: next once, Fast: next twice. Do-while loop (both start at n). If meet at 1: happy. Else: cycle. O(log n) time, O(1) space!
⚡ Quick Implementation:
class Test {
public boolean isHappy(int n) {
// // Approach 1 - hashset
// // TC: O(log n) and SC: O(log n)
// HashSet<Integer> set = new HashSet<>();
// while (n != 1 && !set.contains(n)) {
// set.add(n); // add the incoming number
// int curr = n;
// int squaresSum = 0;
// // find the sum of squares of number.
// while (curr > 0) {
// int mod = curr % 10;
// squaresSum += Math.pow(mod, 2);
// curr = curr / 10;
// }
// n = squaresSum;
// }
// return n == 1;
// Approach 2 - using Floyd Algorithm
// TC: O(log n) and SC: O(1)
// Almost same as above. Instead of finding next num one at a time, we
// find 2 next numbers at a time. This gets equivalent to fast and slow
// pointers. When fast pointer lap on the slow pointer, cycle gets
// detected and the number is not happy.
int slow = n;
int fast = n;
while (fast != 1) { // loop till it becomes unhappy.
System.out.println("slow: "+slow+" and fast: "+fast);
slow = getSumOfSquares(slow);
fast = getSumOfSquares(getSumOfSquares(fast));
System.out.println("sslow: "+slow+" and fast: "+fast);
// break once cycle gets detected or
// when happy number found (edge case when both slow and fast are equal)
if(slow == fast && fast != 1) {
return false;
}
}
return true;
}
private int getSumOfSquares(int n) {
int curr = n;
int squaresSum = 0;
// find the sum of squares of number.
while (curr > 0) {
int mod = curr % 10;
squaresSum += Math.pow(mod, 2);
curr = curr / 10;
}
return squaresSum;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.isHappy(19) == true); // T
System.out.println(t.isHappy(2) == false); // F
System.out.println(t.isHappy(1) == true); // T
System.out.println(t.isHappy(2) == false); // F
System.out.println(t.isHappy(7) == true); // T
System.out.println(t.isHappy(116) == false); // F
System.out.println(t.isHappy(10) == true); // T
}
}
🔑 Key Insights:
- Pattern: Fast & Slow Pointers on transformations
- Transform: n → sum of squares of digits
- Implicit List: Each number → next number
- Two Outcomes: Reach 1 (happy) or cycle (not happy)
- Do-While: Both start at n, need to move first
- Meet at 1: Happy! ✓
- Meet elsewhere: Cycle, not happy ✗
- getNext: O(log n) - number of digits
- Time: O(log n), Space: O(1)
🎪 Memory Aid:
"Sum squares of digits! Reach 1 or cycle! Floyd detects both!"
Think: "Implicit linked list with transformations!" 🔄
💡 The Key Insight:
This is a disguised linked list cycle problem!
Each number "points to" its next:
n → getNext(n) → getNext(getNext(n)) → ...
Just like:
node → node.next → node.next.next → ...
Floyd's algorithm works on ANY sequence!
⚠️ Critical Details:
1. Transform: Sum of squares of each digit
2. getNext: Extract digits with % 10, divide by 10
3. Do-While: MUST use (not while)
4. Why? Both start equal, need to move first
5. Meet at 1: Return true (happy)
6. Meet elsewhere: Return false (cycle)
7. Common cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
8. Bounded: Sequences converge quickly
🔥 The getNext Function:
n = 19
Extract digits and square:
19 % 10 = 9 → 9² = 81
19 / 10 = 1
1 % 10 = 1 → 1² = 1
1 / 10 = 0 (done)
Sum: 81 + 1 = 82 ✓
💡 Why Do-While:
Initial state:
slow = 19
fast = 19
If using while (slow != fast):
19 != 19? No! Loop exits immediately ✗
Using do-while:
Move first, THEN check
Always executes at least once ✓
After first iteration:
slow = 82
fast = 100
Now they're different, loop continues ✓
🎯 Common Unhappy Cycle:
Most unhappy numbers end up in this cycle:
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
Examples:
2 → 4 → (enters cycle)
3 → 9 → 81 → 65 → 61 → 37 → (in cycle)
5 → 25 → 29 → 85 → 89 → (in cycle)
Almost all unhappy numbers eventually
reach this 8-number cycle!
🧪 Edge Cases
Case 1: Already happy
Input: n = 1
Output: true
(1² = 1, stays at 1)
Case 2: Simple unhappy
Input: n = 2
Output: false
(2 → 4 → 16 → ... → cycle)
Case 3: Large happy number
Input: n = 7
Output: true
(7 → 49 → 97 → 130 → 10 → 1)
Case 4: Two digits happy
Input: n = 19
Output: true
(19 → 82 → 68 → 100 → 1)
Case 5: Three digits unhappy
Input: n = 116
Output: false
(Enters cycle)
All handled correctly! ✓
Related Patterns
- Linked List Cycle (LC 141) - Explicit linked list
- Find Duplicate Number (LC 287) - Array as implicit list
- Circular Array Loop (LC 457) - Array with indices
Happy practicing! 🎯
Note: This beautifully demonstrates Floyd's algorithm works on ANY sequence, not just linked lists! The transformation function creates an implicit "linked list" structure! 🔄