4.28.4 — Happy Number

LeetCode 202 · Easy

The problem

Repeatedly replace a number by the sum of the squares of its digits. It is happy if this eventually reaches 1, and unhappy if it loops forever.

19  →  1²+9² = 82  →  8²+2² = 68  →  6²+8² = 100  →  1²+0²+0² = 1   →  true
2   →  4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → …               →  false

The pattern

The process is deterministic: each number has exactly one successor. So the sequence either reaches 1 or repeats a value it has already visited — and once it repeats, it is in a cycle forever.

That is 4.9.7 Linked List Cycle with next(n) = the digit-square sum. Any process with a single successor is a linked list, whether or not there are any pointers involved.

Two ways to detect the repeat:

• A set of everything seen. Simple, O(\log n) space.
• Floyd's slow and fast pointers. O(1) space, and the reason this problem is filed where it is.

The digit-square step

def next_number(n: int) -> int:
    total = 0
    while n:
        n, digit = divmod(n, 10)
        total += digit * digit
    return total

divmod(n, 10) peels the last digit and shifts the rest down in one call. This loop is the standard way to walk a number's digits and it appears in half the problems in this chapter.

The solution

Python

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_number(x: int) -> int:
            total = 0
            while x:
                x, digit = divmod(x, 10)
                total += digit * digit
            return total

        slow, fast = n, next_number(n)

        while fast != 1 and slow != fast:
            slow = next_number(slow)
            fast = next_number(next_number(fast))

        return fast == 1

TypeScript

function isHappy(n: number): boolean {
  const next = (x: number): number => {
    let total = 0;
    while (x > 0) {
      const d = x % 10;
      total += d * d;
      x = Math.floor(x / 10);
    }
    return total;
  };

  let slow = n, fast = next(n);

  while (fast !== 1 && slow !== fast) {
    slow = next(slow);
    fast = next(next(fast));
  }

  return fast === 1;
}

The loop ends for one of two reasons, and the return distinguishes them: fast == 1 means happy; slow == fast with fast != 1 means a cycle.

fast starts one step ahead, so the equality test does not fire immediately on the first iteration.

Only fast is checked against 1. It moves faster, so it reaches 1 first if 1 is reachable at all.

The set version

def isHappy(self, n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = next_number(n)
    return n == 1

Shorter, easier to read, O(\log n) space. Write this first, then offer Floyd's when asked about space.

Why the sequence cannot run away to infinity

Worth knowing, because it explains why the problem terminates at all.

For a three-digit number the largest possible digit-square sum is 9^2 \times 3 = 243. For any number with four or more digits the sum is smaller than the number itself — a four-digit number is at least 1,000 while its sum is at most 324.

So every sequence drops below 1,000 within a few steps and stays there. With a finite set of reachable values and a deterministic step, the sequence must eventually repeat. It cannot escape upwards.

In fact every unhappy number falls into the same single cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. So a valid solution is to check whether the sequence ever hits 4. It works, and it relies on a fact you would have to look up — mention it as a curiosity, not as your answer.

Complexity

O(\log n) time for the first step — the number of digits — and then a bounded number of steps, since values quickly fall below 1,000.

O(1) space with Floyd's; O(\log n) with the set.

Where this goes next

The technique — treat a deterministic process as a linked list and use cycle detection — is the transferable part:

• Linked List Cycle — the original. 4.9.7.
• Find the Duplicate Number — an array read as a function from index to index. 4.9.8.
• Pseudorandom number generators — Floyd's is how you measure a generator's period, and a short period is a real defect.
• Detecting infinite loops in a state machine — the same test.

What the interviewer will push on

"How do you know it terminates?" Values above 1,000 shrink, so the sequence is confined to a finite set and must repeat.

"Why does cycle detection apply?" Each number has exactly one successor, which is a linked list.

"Can you do it in O(1) space?" Floyd's slow and fast.

"Why check only fast against 1?" It moves faster, so it arrives first.

"Is there a shortcut?" Every unhappy number reaches 4. Say it is a looked-up fact rather than a derivation.

One thing to volunteer: say "this is a linked list without pointers" before writing anything. It reframes an arithmetic puzzle as a problem you already solved, which is the whole point of pattern recognition.

Next: 4.28.5 Plus One — the shortest problem in the chapter, with exactly one interesting input.