Happy Number
Bhagavad Gita — The Wheel of Samsara — Does the Soul Reach Moksha or Loop Forever?
जन्म कर्म च मे दिव्यमेवं यो वेत्ति तत्त्वतः। त्यक्त्वा देहं पुनर्जन्म नैति मामेति सोऽर्जुन॥
*One who truly knows My divine birth and actions, O Arjuna, having left the body, is not born again — they attain Me.*
The Story
In Yama's court, the Lord of Death judged souls with the precision of a mathematician. Each soul arrived with its accumulated karma score — a number. The test was this: through the process of dharmic refinement, would the soul's number eventually reduce to 1, the indivisible divine unity? Or would it loop forever in the cycle of rebirth?
The refinement process was specific: take each digit of the soul's karma number, square it, and sum the squares. Repeat. A soul with number 19: 1² + 9² = 1 + 81 = 82. Then 8² + 2² = 64 + 4 = 68. Then 6² + 8² = 36 + 64 = 100. Then 1² + 0² + 0² = 1. Reached 1! This soul attains moksha — it is a "happy number."
But some souls, like those bound deeply to samsara, enter an endless loop: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4... and back to 4! They cycle forever, never reaching 1.
Chitragupta, the meticulous record-keeper, faced a queue of a thousand souls awaiting judgment. For each soul, he needed to determine: moksha-bound or samsara-trapped?
A junior record-keeper suggested the obvious method: "Keep a list of all karma values we've seen for this soul. If we see a repeated value, it's a cycle — samsara. If we reach 1, moksha."
"And if the soul's number cycles through ten thousand values before repeating?" Chitragupta asked gently. "We would need ten thousand entries in our list for a single soul. With a thousand souls to judge today, that is ten million memory entries."
"Then... we cannot know?"
"We can know with O(1) space," Chitragupta replied. "Watch."
He summoned two messengers. "You," he told the first, "will trace this soul's karmic refinement one step at a time. You," he told the second, "will trace it two steps at a time — always applying the refinement twice for every once the first does."
Both messengers began with karma value 19.
The slow messenger: 19 → 82 → 68 → 100... The fast messenger: 19 → 68 → 100 → 1 (fast messenger reached 1! The number is happy!)
But consider a non-happy number like 2: Slow: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42... Fast: 2 → 16 → 58 → 145 → 20 → 37 → ...
Eventually, both enter the cycle {...37→58→89→145→42→20→4→16→37...} and the fast pointer laps the slow one — they MEET at some value.
"If the fast messenger reaches 1, it is a happy number — moksha is granted," Chitragupta explained. "If the fast and slow messengers ever point to the same value (and it's not 1), they are both trapped in the cycle — the soul is samsara-bound."
Ashwini Kumar, the divine physician who was attending court, asked: "But what if the fast pointer reaches 1 while the slow is still traveling? Does that mean happiness?"
"Precisely. If fast == 1, we stop immediately and declare it happy. We need not wait for slow to catch up to 1. The fast pointer will always reach 1 before the slow one if the number is happy."
"And the loop detection works because?"
"Because within any cycle, the fast pointer is moving 2 steps for every 1 of the slow pointer. Their relative distance within the cycle decreases by 1 each round. They must meet."
Soul after soul was judged. The fast-slow messenger system hummed with efficiency. Numbers that were truly happy (like 1, 7, 10, 13, 19, 23...) granted their souls liberation. Numbers trapped in the cycle of samsara were marked for another birth.
"This is the wisdom of the Gita," Chitragupta mused. "Some paths lead to the divine unity of 1. Others loop eternally through the same karmic patterns. The fast-slow detector reveals which path we're on — without needing to remember every step we've taken."
This is the Fast & Slow Pointer technique for detecting Happy Numbers.
The Junior Clerk's First Instinct
Store every karma value seen in a HashSet. If we see it again, it's a cycle (not happy). If we reach 1, it's happy. Uses O(n) space proportional to the cycle length.
public boolean isHappyBruteForce(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1) {
if (seen.contains(n)) {
return false; // We've looped — not happy
}
seen.add(n);
n = sumOfSquaredDigits(n);
}
return true; // Reached 1 — happy!
}
private int sumOfSquaredDigits(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}Chitragupta's Wisdom
public boolean isHappy(int n) {
int slow = n;
int fast = getNext(n); // Fast starts one step ahead
// Continue until fast reaches 1 (happy) or slow catches fast (cycle)
while (fast != 1 && slow != fast) {
slow = getNext(slow); // One karma refinement
fast = getNext(getNext(fast)); // Two karma refinements
}
return fast == 1; // Reached moksha, or caught in cycle?
}
// Compute sum of squares of digits (one karma refinement step)
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit; // Square each digit
n /= 10;
}
return sum;
}
// Test cases
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.isHappy(19)); // true (19→82→68→100→1)
System.out.println(sol.isHappy(2)); // false (2→4→16→37→58→89→145→42→20→4...)
System.out.println(sol.isHappy(7)); // true
}Step-by-Step Walkthrough
n = 19
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
getNext(19) = 1² + 9² = 1 + 81 = 82
getNext(82) = 8² + 2² = 64 + 4 = 68
getNext(68) = 6² + 8² = 36 + 64 = 100
getNext(100) = 1² + 0² + 0² = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial: slow=19, fast=getNext(19)=82
Round 1: slow=82, fast=getNext(getNext(82))=getNext(68)=100
slow≠fast, fast≠1, continue
Round 2: slow=68, fast=getNext(getNext(100))=getNext(1)=1
fast==1 → HAPPY! ✅
✅ Return true (19 is a happy number)Deep Insight
**Why does every unhappy number eventually cycle?**
For any starting number with d digits, the next number has at most 81d (since max digit is 9, 9²=81). For 3-digit numbers, next ≤ 243. For numbers ≤ 243, next ≤ 243. So all unhappy numbers eventually fall into the range [1,243] and must cycle (only finitely many values). The cycle of unhappy numbers always includes 4: `4→16→37→58→89→145→42→20→4`.
**The getNext function runs in O(log n)** because the number of digits is log₁₀(n).
**Why does fast reach 1 first for happy numbers?** In a non-cyclic sequence approaching 1, fast is simply further along the path and reaches the end (1) first.
**Edge cases:** - n=1: fast starts at getNext(1)=1, immediately returns true - n=0: Not a valid input (problem says positive integer) - Large numbers: Eventually enter the 3-digit range
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(log n) per step × O(cycle length) steps | O(cycle length) | HashSet grows with each unique value seen |
| Optimal | O(log n) | O(1) | Only two integer variables — slow and fast |
Pattern Recognition
✅ Sequence that either terminates at a target or loops ✅ No explicit linked list, but can be modeled as one ✅ Cycle detection required with O(1) space ✅ "Eventually" + "cycle" + O(1) space **LeetCode Trigger Phrases:** → "determine if a number is happy" → "process repeats... eventually reaches 1 or loops forever" → "sum of squares of digits"
Bhagavad Gita 4.9
जन्म कर्म च मे दिव्यमेवं यो वेत्ति तत्त्वतः। त्यक्त्वा देहं पुनर्जन्म नैति मामेति सोऽर्जुन॥
One who truly knows My divine birth and actions, O Arjuna, having left the body, is not born again — they attain Me.
Connection: The Happy Number algorithm is a perfect computational metaphor for moksha and samsara. Happy numbers are those whose karmic refinements (sum of squared digits) inevitably lead to 1 — the divine unity, liberation, moksha. Unhappy numbers loop endlessly through the same karmic patterns — samsara, rebirth, the cycle that never ends. The fast-slow detector, like divine discernment, determines which path a soul is on — without needing to record every life it has lived.