Math & Geometry crash course ↗ · 127

202. Happy Number

A number is "happy" if repeatedly replacing it with the sum of its squared digits eventually reaches 1. The trick is recognising that unhappy numbers always fall into a cycle— detect it with a seen-set or Floyd's fast/slow pointers and you're done.

● EasyHash Set / Cycle DetectionFloyd Two-PointerTypeScript

PROBLEM What we're solving

Write a function that returns true if a positive integer n is a happy number. Starting from n, repeatedly replace it with the sum of the squares of its digits. If the process eventually produces 1, the number is happy; otherwise it cycles forever and we return false.

Worked example — n = 19:

  • 1² + 9² = 82
  • 8² + 2² = 68
  • 6² + 8² = 100
  • 1² + 0² + 0² = 1 ✓

Result: true. For n = 2 the sequence eventually hits 4 → 16 → … → 4 — a cycle, so false.

KEY IDEA Every unhappy number cycles — so just detect the cycle

Insight → for any starting number, the digit-square process either reaches 1 (happy) or enters an infinite loop (unhappy). Unhappy numbers always pass through 4, then repeat the same sequence. This means cycle detection is the whole problem. Store each value in a Set; if you see a value twice before reaching 1, you're in a cycle → return false.

RECIPE Simulate with a seen-set

  • 1 · Initialise. Create an empty Set<number>. This is your cycle detector.
  • 2 · Loop while n ≠ 1. Each iteration is one step of the process. We stop as soon as we reach 1 (happy).
  • 3 · Check the seen set. Before updating n, test seen.has(n). If the value already appeared, we've entered a cycle → return false.
  • 4 · Record and advance. Add n to seen, then set n = sumOfSquaredDigits(n).
  • 5 · Return true. The loop exited because n === 1 — the number is happy.
Classic confusion → people forget to add n to seen before advancing, or they check seen.has(n) after advancing — then the set stores next-step values and the cycle check never fires on the right value. Always: check → add → advance.

COST Complexity & alternatives

No termination guard
∞ loop
Naively iterating without cycle detection runs forever for unhappy numbers.
Seen-set or Floyd
O(log n)
O(log n) time per step; O(log n) space for the seen-set, O(1) for Floyd.

Space trade-off

The seen-set approach uses O(log n) space (the number of unique values before a cycle is bounded by the size of the value, which shrinks to at most 3 digits quickly). For true O(1) space, use Floyd's cycle detection: slow takes one step, fast takes two. If they ever meet at a value other than 1, it's a cycle. If fast reaches 1, it's happy.

Pattern transfer →the same "detect a cycle in a functional sequence" idea appears in Find the Duplicate Number (Floyd on an implicit linked list of array indices), Linked List Cycle (fast/slow pointers), and Circular Array Loop. Whenever a deterministic process on a finite domain can repeat, Floyd applies.

RUN IT Trace the digit-square process and detect cycles

step 0 / 9
STARTStart with 19. We'll repeatedly replace n with the sum of squared digits until we reach 1 (happy) or revisit a number (cycle → unhappy).
1▶function isHappy(n: number): boolean {
2▶  const seen = new Set<number>();
3  while (n !== 1) {
4    if (seen.has(n)) return false; // cycle detected
5    seen.add(n);
6    n = sumOfSquaredDigits(n);
7  }
8  return true;
9}
10 
11function sumOfSquaredDigits(n: number): number {
12  let sum = 0;
13  while (n > 0) {
14    const d = n % 10;
15    sum += d * d;
16    n = Math.floor(n / 10);
17  }
18  return sum;
19}
19n
State
19
n
{}
seen
current n / next value / sumjust added to seenreached 1 (happy)cycle detected (unhappy)
slowfast

TYPESCRIPT The solution, annotated

isHappy.ts
function isHappy(n: number): boolean {
  const seen = new Set<number>();
  while (n !== 1) {
    if (seen.has(n)) return false; // cycle detected
    seen.add(n);
    n = sumOfSquaredDigits(n);
  }
  return true;
}

function sumOfSquaredDigits(n: number): number {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

Reading it block by block

Lines 2 — the cycle detector. A Set<number>stores every value we've seen. Once a value recurs we know we're looping. Without this, the process for unhappy numbers never terminates.
Lines 3–7 — main loop. We run as long as n !== 1. Inside: check the set first (cycle → false), then add n, then advance. This exact order prevents the classic off-by-one where you add after advancing and miss the cycle.
Line 8 — return true. The only way to exit the loop is n === 1, so we know the sequence reached the happy ending.
Lines 12–19 — sumOfSquaredDigits. Extract each digit with n % 10, square it, add to sum, then floor-divide to discard that digit. This is O(log n) — one iteration per digit.
Complexity → Each call to sumOfSquaredDigits is O(log n) (one step per digit). For a starting number n, the value drops to at most 3 digits after the first step, so the chain length before hitting 1 or a cycle is bounded by a constant for any practical input — effectively O(log n) total time. The seen-set uses O(log n) space; Floyd's variant uses O(1).

INTERVIEWFollow-ups they'll ask

  • "Can you do it in O(1) space?"Use Floyd's two-pointer approach: slow = step(n), fast = step(step(n)), advance until they meet or fast === 1.
  • "What if the input is huge (e.g. 10¹⁸)?"The sum of squared digits of a k-digit number is at most 81k, so any number > 1000 shrinks dramatically on the first step. The chain is short regardless of starting size.
  • "Which numbers are always in the unhappy cycle?" Every unhappy number eventually passes through 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … This is provable; knowing it lets you hard-code a fast exit.
  • "How would you test this?" Check that 1 returns true immediately; 19 is the smallest two-digit happy number; 2 is the smallest unhappy number.

MNEMONIC The one-liner

"Check before you add, add before you advance — then 1 is happy, a repeat is a trap."

TRIGGERS When you see ___ → reach for ___

"repeatedly apply a function until a condition"seen-set cycle detection
"infinite loop in a finite domain"Floyd's fast/slow pointers
"sum of digit squares"extract digits with % 10, floor / 10
"does the process terminate or cycle?"seen-set or Floyd on the sequence

SKELETON The reusable shape

skeleton.ts
function isHappy(n: number): boolean {
  const seen = new Set<number>();
  while (n !== 1) {
    if (seen.has(n)) return false;
    seen.add(n);
    n = sumOfSquaredDigits(n);
  }
  return true;
}

function sumOfSquaredDigits(n: number): number {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

FLASHCARDS Tap to flip

What makes a number "happy"?
Repeatedly replacing it with the sum of squared digits eventually reaches 1.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the result of running the happy-number process on n = 19?
QUESTION 02
Why must we add n to the seen-set before computing the next value?
QUESTION 03
What is the time complexity of isHappy for an input n?
QUESTION 04
How does Floyd's two-pointer approach detect an unhappy cycle?
QUESTION 05
For the seen-set solution, what is the space complexity?
QUESTION 06
Which of the following is the smallest unhappy number?
QUESTION 07
What does sumOfSquaredDigits(13) return?
QUESTION 08
#202 · Happy NumberRepeatedly replace a number with the sum of the squares of its digits. Use a hash set to detect a cycle; the number is happy iff the process eventually reaches 1.Which algorithmic approach does this primarily use?
QUESTION 09
#202 · Happy NumberRepeatedly replace a number with the sum of the squares of its digits. Use a hash set to detect a cycle; the number is happy iff the process eventually reaches 1.Which implementation correctly solves it?