Happy Number
Decide whether repeatedly summing the squares of a number's digits reaches 1, using Floyd's slow and fast pointers to detect the loop.
Problem Understanding
Happy Number: replace a number with the sum of the squares of its digits, and repeat. The number is happy if this eventually reaches 1, and not happy if it loops forever without reaching 1.
Examples: 19 → 82 → 68 → 100 → 1, so 19 is happy. 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … loops, so 2 is not.
The Intuition: The Sequence Is a Linked List
Every number has exactly one next number, so the sequence from n is a linked list. It cannot grow forever (big numbers shrink quickly), so it either reaches 1, which points to itself, or enters a loop that avoids 1.
That is exactly what Linked List Cycle detects. Use Floyd's two pointers:
slowstarts atn,fastone step ahead.- While
fast != 1andslow != fast: moveslowone step andfasttwo. - If
fastreached 1, the number is happy; if they met first, it is caught in a loop.
No set is needed: two integers are enough.
Interactive Walkthrough
EACH VALUE → SUM OF THE SQUARES OF ITS DIGITS
SLOW AT n, FAST ONE AHEAD
s
→
f
→
→
→
slow
19
fast
82
Happy?
—
slow starts at 19; fast starts one step ahead at 82, the sum of the squares of 19's digits
Next
slow takes one step to 82; fast takes two to 100
n
Legend & Complexity
slow (s)
fast (f)
1: the number is happy
Time
O(log n)
Space
O(1)
The sequence is drawn as a chain until it reaches 1 or repeats; a repeat shows where it loops back. s and f mark the two pointers. Try 2 to watch them meet inside the loop.
Dry Run Table
Input: n = 19
| Step | slow | fast |
|---|---|---|
| start | 19 | 82 |
| 1 | 82 | 100 |
| 2 | 68 | 1 |
fast reached 1, so 19 is happy.
The Solution Template
Floyd's tortoise and hare on the digit-square sequence.
Happy Number Code
1var isHappy = function(n) {2 const next = (x) => {3 let sum = 0;4 for (; x > 0; x = Math.floor(x / 10)) sum += (x % 10) ** 2;5 return sum;6 };7 let slow = n, fast = next(n);8 while (fast !== 1 && slow !== fast) {9 slow = next(slow);10 fast = next(next(fast));11 }12 return fast === 1;13};
Edge Cases & Common Mistakes
- n = 1: happy immediately;
faststarts at 1 and the loop never runs. - Starting slow and fast at the same value: the loop condition
slow != fastwould stop at once; startfastone step ahead. - Checking
slow == 1: fast reaches 1 first; testfast. - Looping forever: without cycle detection (Floyd or a set), an unhappy number never terminates.
Summary
The digit-square sequence is a linked list that ends at 1 or in a loop. Move slow one step and fast two; return true if fast reaches 1, false if the pointers meet first. O(log n) per step, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet