Happy Number Solution

Problem

Starting from any positive integer, repeatedly replace it with the sum of the squares of its digits. If this process eventually reaches 1, the number is "happy"; otherwise the sequence loops forever in a cycle that never includes 1.

Input: n = 19
Output: true
Explanation: 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1

Counter-example showing a cycle: n = 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (back to 4, cycles forever → false).

Intuition

The core challenge is knowing when to stop — for unhappy numbers, the sequence never reaches 1 but also never grows unboundedly. All unhappy numbers eventually land in a fixed cycle. This means the problem reduces to cycle detection: either we find 1 (happy) or we detect a repeated value (unhappy). The two approaches differ only in how they detect that cycle.

Approach 1 — Hash Set

Track every number we've seen. If we see the same number twice before reaching 1, we've confirmed a cycle and can return false immediately.

Add the current number to a seen set.
Compute the next number: sum of squares of each digit.
If the next number is 1, return true.
If the next number is already in the seen set, return false.
Otherwise, add it to the set and repeat.

1def isHappy(n: int) -> bool:
2    def get_next(num: int) -> int:
3        digit_square_sum = 0
4        while num > 0:
5            digit = num % 10
6            digit_square_sum += digit * digit
7            num //= 10
8        return digit_square_sum
9
10    seen = set()
11    while n != 1:
12        if n in seen:
13            return False          # revisited a value — confirmed cycle
14        seen.add(n)
15        n = get_next(n)
16    return True

Time: O(log n) — large numbers shrink quickly; after the first step, all values stay under ~243, so the cycle is bounded by a small constant.

Space: O(log n) — the set stores at most a bounded number of values before a cycle is found, but technically O(1) in practice since cycles are short.

Approach 2 — Floyd's Cycle Detection

Use two pointers, slow and fast. Slow advances one step at a time; fast advances two steps. In any sequence with a cycle, fast eventually laps slow and they meet. If fast reaches 1 first, there is no cycle.

Initialize slow to n, fast to getNext(n).
While fast is not 1 and slow ≠ fast: advance slow one step, fast two steps.
Return fast == 1.

1def isHappy(n: int) -> bool:
2    def get_next(num: int) -> int:
3        digit_square_sum = 0
4        while num > 0:
5            digit = num % 10
6            digit_square_sum += digit * digit
7            num //= 10
8        return digit_square_sum
9
10    slow = n
11    fast = get_next(n)           # start fast one step ahead to avoid immediate equality
12    while fast != 1 and slow != fast:
13        slow = get_next(slow)
14        fast = get_next(get_next(fast))
15    return fast == 1

Time: O(log n) — same as the hash set approach; fast pointer reaches the cycle and meets slow in bounded steps.

Space: O(1) — only two integer pointers, no auxiliary storage.

Complexity Summary

Approach	Time	Space	When to use
Hash Set	O(log n)	O(log n)	Clearest intent; preferred in most interview settings
Floyd's Cycle Detection	O(log n)	O(1)	When the interviewer asks for a constant-space solution

Common Mistakes

Starting both pointers at the same position in Floyd's — if you initialize slow = n and fast = n, the loop exits immediately because slow == fast, and you return fast == 1 which is wrong for n > 1. Fast must start one step ahead: fast = get_next(n).
Looping a fixed number of times instead of using cycle detection — a hard-coded limit like for _ in range(1000) will give wrong answers for edge cases and is not a correct solution.
Forgetting n //= 10 inside the digit extraction loop — without this, the loop runs forever extracting the same last digit; the integer-divide step advances to the next digit.
Checking fast == 1 inside the loop instead of after — the condition fast != 1 in Floyd's while-guard already covers this, but factoring it wrong can cause you to miss the happy case.
Assuming only n=1 terminates the happy sequence — it does, but it helps to understand why: once you reach 1, get_next(1) = 1, so the sequence stays at 1 indefinitely. The check n == 1 at the top of the loop (or fast == 1 in Floyd's) is correct for exactly this reason.

Happy Number — Solution