Happy Number: Cycle Detection with a Hash Set

LeetCode 202. Happy Number asks you to determine whether a positive integer eventually reaches 1 when you repeatedly replace it with the sum of the squares of its digits. If it reaches 1, the number is "happy." If it never does, it is stuck in an endless cycle.

The trick is recognizing that this is a cycle detection problem in disguise.

Why does it cycle?

You might wonder: could the sequence just grow forever without repeating? It turns out it cannot. For any number with d digits, the maximum sum of digit squares is d * 81 (since 9^2 = 81). A 3-digit number can produce at most 243, a 4-digit number at most 324. So the sequence always drops below a few hundred and stays there. With a bounded range and infinite steps, repetition is guaranteed by the pigeonhole principle.

That means there are only two outcomes: you hit 1, or you enter a cycle that does not include 1.

Approach 1: Hash set (detect the cycle)

Keep a set of every number you have seen. Each iteration, compute the next number in the sequence. If it equals 1, return True. If it is already in your set, you have found a cycle, so return False. Otherwise, add it to the set and continue.

def is_happy(n: int) -> bool:
    seen = set()
    while n != 1:
        if n in seen:
            return False
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return True

This is the same "seen set" pattern you use in Contains Duplicate and dozens of other problems. The only difference is what you are tracking: instead of array values, you are tracking computed results in a sequence.

Visual walkthrough: n = 19

Let's trace through the hash set approach step by step with n = 19.

Four iterations and we reach 1. The seen set never encountered a repeat, so no cycle formed. 19 is happy.

A cleaner digit-square helper

Converting to a string works, but you can also extract digits with modular arithmetic. This avoids string allocation and is a useful building block on its own.

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

Plug this into the main function:

def is_happy(n: int) -> bool:
    seen = set()
    while n != 1:
        if n in seen:
            return False
        seen.add(n)
        n = digit_square_sum(n)
    return True

Approach 2: Floyd's tortoise and hare (O(1) space)

If you have solved Linked List Cycle, you already know Floyd's algorithm. The idea is the same: use a slow pointer that advances one step and a fast pointer that advances two steps. If there is a cycle, they will eventually meet. If the fast pointer hits 1, the number is happy.

def is_happy(n: int) -> bool:
    def next_num(x: int) -> int:
        total = 0
        while x > 0:
            x, digit = divmod(x, 10)
            total += digit * digit
        return total

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

No set needed. The space complexity drops from O(n) to O(1), while time remains linear.

Complexity analysis

Here k is the number of steps before reaching 1 or detecting a cycle. In practice, k is small (bounded by a constant for any input, since the sequence quickly drops below 243). Each step costs O(log n) to extract digits. Both approaches run fast enough for any input LeetCode throws at you.

Building blocks

This problem decomposes into two reusable pieces that you will see again and again.

1. Cycle detection (seen set or Floyd's)

The core question is: "Have I visited this state before?" Whether you use a hash set or two pointers, the pattern is identical. You will use it in linked list problems, graph traversal, and anywhere a process might loop.

seen = set()
while state not in seen:
    seen.add(state)
    state = next_state(state)

2. Digit extraction

Pulling individual digits out of a number using repeated division and modulo. This micro-pattern shows up in problems like "add digits," "reverse integer," and "palindrome number."

while n > 0:
    n, digit = divmod(n, 10)
    # process digit

On CodeBricks, you drill each building block separately. When they show up combined in a problem like Happy Number, you recognize both pieces instantly.

Edge cases

• n = 1: Already happy. The while loop never executes, and you return True immediately.
• n = 7: Happy. The chain is 7 -> 49 -> 97 -> 130 -> 10 -> 1.
• Single-digit happy numbers: Only 1 and 7 are happy among single-digit numbers. Every other single digit enters the cycle containing 4.

From understanding to recall

Reading through this solution is the easy part. The harder part is being able to reproduce it under pressure, two weeks from now, when you see a problem that requires cycle detection or digit extraction.

That is what spaced repetition solves. CodeBricks breaks Happy Number into its two building blocks and drills them at increasing intervals. You type each piece from scratch, not from memory of the full solution, but from understanding the pattern. After a few review cycles, "detect a cycle with a seen set" and "extract digits with divmod" become automatic.

Related posts

• Linked List Cycle - Floyd's tortoise and hare algorithm applied to linked lists, the same cycle detection idea used here
• Contains Duplicate - The simplest "seen set" problem, the same pattern that powers the hash set approach in Happy Number