Happy Number: Cycle Detection Without a Linked List

"Happy Number" shows up again and again in Google, Airbnb, Adobe phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Fast and Slow Pointers pattern quickly and code it cleanly. Part 4 of 11 in the Fast and Slow Pointers arc.

The Problem

A happy number repeatedly replaces itself with the sum of the squares of its digits; happy numbers reach 1, unhappy ones loop forever. Given n, return whether it is happy. The lesson: the pattern applies to any iterated function, not just pointer chains.

Input:  n = 19
Output: True
19 -> 82 -> 68 -> 100 -> 1

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

The sequence n, f(n), f(f(n)), ... either reaches a fixed point or enters a cycle — structurally identical to a linked list where next is a function. Unhappy numbers are a cycle, so detect the cycle in O(1) space instead of storing seen values.

The Approach

Run slow at f and fast at f∘f until they meet; happiness is simply whether the meeting value is 1. The set-of-seen-values answer is perfectly acceptable as a first pass — offer Floyd as the space upgrade, which is exactly the conversation the interviewer wants.

Digit-square sums of numbers below 1000 stay below 244, so the state space is tiny and termination is guaranteed — a sentence of justification that reads as rigor.

Python Solution

def is_happy(n: int) -> bool:
    """True if iterating digit-square-sum from n reaches 1."""

    def step(x: int) -> int:
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, step(n)
    while fast != 1 and slow != fast:
        slow = step(slow)
        fast = step(step(fast))
    return fast == 1

Complexity

• Time: O(log n) per step, bounded total — values collapse below 244 after one step, giving a constant-size state space
• Space: O(1) — two integers instead of a seen-set

Interview Tips and Follow-Ups

• Every unhappy number falls into the known cycle containing 4 — checking x == 4 is a cute constant-space alternative worth mentioning.
• Generalize when prompted: detecting convergence of any iterated function (pseudo-random generators, transformation chains) is the same code.
• divmod keeps digit extraction clean in Python — small fluency signals add up in screens.

If this clicked, continue the Fast and Slow Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.