Happy Number

Problem

Define one step on a positive integer as: replace the number by the sum of the squares of its digits. A number is happy if repeatedly applying this step eventually reaches 1. If the process instead falls into a loop that never contains 1, the number is not happy. Given n, return True if it is happy, otherwise False.

Examples

• n = 19 → True — 19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1.
• n = 2 → False — the sequence 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... cycles back to 4 without ever hitting 1.
• n = 7 → True — 7 → 49 → 97 → 130 → 10 → 1.

Constraints

• 1 <= n <= 2^31 - 1

Think about it first

TL;DR

Iterate the digit-square-sum step and detect a cycle — with a hash set (O(log n) time/space) or Floyd’s cycle detection (O(1) space).

Approach 1 — Cycle detection with a hash set

The sequence is fully determined by the current value, so if a value ever repeats, everything after it repeats forever. Remember every value seen; stop when you reach 1 (happy) or revisit a value (not happy).

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

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = next_num(n)
    return n == 1

Walkthrough with n = 19: 19 → 82 → 68 → 100 → 1. No repeat before reaching 1, so the loop exits with n == 1 → True. For n = 2, the sequence eventually produces 4 a second time; at that point n in seen, the loop exits with n != 1 → False. That non-happy sequence forms a closed cycle:

flowchart LR
    A[4] --> B[16] --> C[37] --> D[58] --> E[89] --> F[145] --> G[42] --> H[20] --> A

Complexity: O(log n) digits per step, and the values quickly drop below 243 (the max digit-square-sum for any number under 1000), so the sequence length before repeating is bounded by a constant. Effectively O(log n) time, O(log n) space for the set.

Approach 2 — Floyd’s tortoise and hare (O(1) space)

“Reaches 1 or cycles” is structurally identical to “does a linked list have a cycle,” where next_num is the next pointer. Floyd’s algorithm walks a slow pointer one step and a fast pointer two steps per iteration; if there is a cycle they eventually land on the same value, and if the sequence terminates the fast pointer reaches the fixed point 1 (since next_num(1) == 1).

def isHappy(n: int) -> bool:
    def next_num(x: int) -> int:
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        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

Walkthrough with n = 2: slow follows 2, 4, 16, 37, ... and fast runs twice as fast through 4, 16, 58, 145, .... Because the 4 → ... → 4 loop is closed, the two pointers eventually coincide on some value that is not 1, so fast != 1 and we return False. With n = 19, fast reaches 1 first, the loop condition fast != 1 breaks, and we return True.

Complexity: O(log n) time (same bounded iteration count, constant work per step aside from digit processing), O(1) space — no set required.

Common pitfalls

• Recomputing the digit-square-sum incorrectly, e.g. summing digits instead of squares of digits.
• Forgetting that 1 is the target: with the set version you must test n == 1 as the success exit, not just “no repeat.”
• In Floyd’s version, initializing slow and fast to the same value and checking equality before advancing — the loop would exit immediately. Start fast one step ahead.

Pattern takeaway

A deterministic sequence x → f(x) on a finite (or eventually bounded) domain must either hit a fixed target or enter a cycle. Detect the cycle either by memorizing visited states (hash set) or, for O(1) space, by Floyd’s tortoise-and-hare — the same trick used for cycle detection in linked lists.