Happy Number (LeetCode 202)

The problem

Take a positive integer n. Replace it with the sum of the squares of its digits, and repeat. If you eventually reach 1, the number is happy; return True. If the process loops forever without reaching 1, return False.

Input:  19
Output: True

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

Starting from 2 instead, the sequence goes 2, 4, 16, 37, 58, 89, 145, 42, 20, 4, … and repeats without hitting 1, so is_happy(2) is False.

How to think about it

Start with brute force. Just simulate. The worry is “how do I know when to stop?” If the number is unhappy, the loop never ends. Capping it at, say, 1,000 steps works in practice but is a guess, not a proof.

The key insight: the sequence is a linked list in disguise. Each number has exactly one “next” number (its digit-square sum). Following next from n either reaches 1 (and 1 maps to itself) or falls into a loop. That is exactly the shape of a linked list that either ends or has a cycle. The values also stay small: any number with d digits maps to at most 81·d, so after a few steps everything is below a few hundred, and a repeat is guaranteed.

So detect the cycle. You can remember every value in a set (see the alternative below), or use tortoise and hare: s applies the function once per tick, f applies it twice. Either f reaches 1, or f laps s inside a loop that does not contain 1. Both outcomes end the loop, and you return whether f is 1.

Which pattern is this? Fast & slow pointers on an implicit sequence. The tell is “repeatedly apply a function; does it loop?”

Approach

1. Define sq(x): the sum of the squares of the digits of x.
2. Start s = n and f = sq(n) (one step ahead, so the loop condition is not true at the start).
3. While f is not 1 and s differs from f: move s one step and f two steps.
4. Return f == 1.

Solution

def is_happy(n):
    def sq(x): return sum(int(d)**2 for d in str(x))   # one step of the sequence
    s = n; f = sq(n)                                   # fast starts one step ahead
    while f != 1 and s != f:
        s = sq(s); f = sq(sq(f))                       # slow 1 step, fast 2 steps
    return f == 1
# is_happy(19) -> True ; is_happy(2) -> False

Alternative: hash set of seen values

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)                                    # remember every value
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1
# is_happy(19) -> True

This version is easier to explain and equally fast. It stores every value it sees, but because the values quickly drop below a few hundred, the set stays small. The fast/slow version uses truly O(1) memory, which is the answer an interviewer probing this lesson wants to hear.

Dry run

The fast/slow version on n = 19:

It returns True. For n = 2, the loop runs seven times and ends with s = f = 42, a meeting inside the cycle, so it returns False.

Complexity

• Time: O(log n) per step. sq touches each digit, and n has O(log n) digits. After the first step the values are small, so the number of steps before reaching 1 or meeting in the cycle is bounded by a constant; overall it is O(log n).
• Space: O(1) for fast/slow. The seen-set version stores a bounded number of small values.

Edge cases and pitfalls

• n = 1: f = sq(1) = 1, so the loop never runs and it returns True.
• Starting both pointers at n makes s != f false immediately, so the loop exits and returns False for every input except 1. Start fast one step ahead, as the code does.
• Check f, not s, for 1. Fast reaches 1 first, and 1 maps to itself, so f == 1 is the right test.
• Hard-coding the cycle (for example, checking for 4) works for this exact function but shows no understanding. Use a general cycle check.

Related problems

• Linked List Cycle (LeetCode 141): the same tortoise and hare on real nodes.
• Find the Duplicate Number (LeetCode 287): another implicit “next” function, this time i -> nums[i].
• Circular Array Loop (LeetCode 457): cycle detection on index jumps, with extra rules.