Happy Number

Happy Number looks like a number puzzle, but it is really a disguised cycle-detection problem. It teaches a clean way to decide whether a process terminates or loops forever: remember every state you have visited.

The slow way first

The naive worry is: how do I know when to stop? If a number is not happy, the chain goes on forever. Without a stopping rule, a simple loop would never terminate. We need a way to detect that we are going in circles.

The question to ask: have I produced this exact number before? If a value ever repeats, the chain from that point on will repeat too — it is a cycle, and it will never reach 1. So the moment we revisit a number, we can safely answer not happy.

The idea: remember every number you have seen

Keep a set of every value the chain has produced. Each turn, replace n with the sum of the squares of its digits. Stop when either n becomes 1 (happy) or n is already in the set (a cycle — not happy). The set is what turns an endless process into a finite one.

The key insight: a set gives us O(1) membership checks, so detecting the cycle costs almost nothing.

Walk through it

Step through the animation. The pointer n moves along the chain 19 → 82 → 68 → 100 → 1. Each value is added to seen before we compute the next one. As soon as the value becomes 1, the loop stops and we return True.

Pseudocode

make an empty set called "seen"
while n is not 1 and n is not in seen:
    add n to seen
    split n into its digits
    n = sum of (each digit squared)
return whether n is now equal to 1

The Python solution

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        digits = [int(d) for d in str(n)]
        n = sum(d * d for d in digits)
    return n == 1

• seen is a set of every value the chain has produced so far.
• Line 3 is the dual stop condition: leave the loop when n reaches 1, or when n repeats (a cycle).
• seen.add(n) records the current value before we transform it.
• str(n) lets us walk the digits as characters; int(d) turns each back into a number.
• n = sum(d * d for d in digits) is the core transform: the sum of squared digits.
• We return n == 1, which is True only if we left the loop because we reached 1.

Complexity

The digit sums shrink quickly and the set of reachable values is bounded, so the chain length is small. The set holds those few visited values, giving O(log n) extra space.

When this pattern shows up

Practice