Happy Number

Signal

A deterministic function applied to a number over and over either converges to a fixed target or falls into a repeating cycle — the same shape as linked-list cycle detection, just walking a numeric sequence instead of .next pointers.

Approach

Repeatedly replace n with the sum of the squares of its digits. Track every value seen in a set; if you land on 1, the number is happy. If you see a value you've already visited before ever reaching 1, you're in a cycle that will never reach 1, so it isn't happy. (Floyd's slow/fast pointer on this same next-value function gets the same answer in O(1) space, trading a bit of clarity for dropping the set.)

Skeleton

seen = set()
while n != 1 and n not in seen:
    seen.add(n)
    n = sum(digit**2 for digit in digits of n)
return n == 1

Solution

def is_happy(n: int) -> bool:
    def next_value(x: int) -> int:
        return sum(int(d) ** 2 for d in str(x))

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

Complexity

O(log n) digits per step, and in practice the sequence enters a small bounded range after the first step or two, so treat the loop as O(1) amortized for interview purposes. O(1) space with Floyd's cycle detection, or O(k) for a seen-set where k is the number of steps before repeating.

Pitfalls

• Assuming an unhappy number loops back to itself — the actual non-happy cycle is a loop through several numbers (4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...), so you must track a set of everything seen, not just check whether you returned to the original n.
• Hand-rolling digit extraction with n % 10 / n //= 10 works but is easy to get wrong on single-digit inputs — str(n) sidesteps that entirely.
• No need to guard against 0 or negative input; the problem guarantees a positive integer.