Happy Number · DSA Prep

The digit-square transform can only ever do one of two things forever: reach 1 and stay there, or fall into a repeating cycle that never includes 1 (it’s a mathematical fact that every starting number eventually does one or the other — the value never grows without bound, since squaring digits caps the result well below the input for any number with more than a few digits). So the whole problem reduces to: detect whether repeating the transform revisits a number it has already produced — if it does, it is caught in a cycle and can never reach 1.

Hash Set to Detect Cycles

Time O(log n)Space O(log n)

Keep applying the digit-square-sum transform, remembering every value seen so far. If the process reaches 1, n is happy. If it produces a value already in the set, it is looping forever without ever hitting 1.

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))
        return n == 1

Trace the first example below — watch how each fresh value joins the chain, and what the moment the chain produces 1 does to the loop:

1 / 5

current n — digits being squaredfresh value, added to the setvalue already in the setrevisited — cycle1 — happy

The loop starts with n = 19 and an empty seen set — 19 is neither 1 nor already seen, so it is recorded as the first chip and its digits are squared next.

None of 19, 82, 68, 100 repeat, and the chain lands on 1, so 19 is happy — the set was never the blocker; the loop’s stop condition simply fired.

Now the same loop on n = 2. Watch for the value the chain eventually produces a second time — that one repetition is the cycle that makes n unhappy:

1 / 7

current n — digits being squaredfresh value, added to the setvalue already in the setrevisited — cycle1 — happy

Same loop, same rules: n = 2 is recorded as the first chip and its digit is squared next. Watch the set closely — this chain ends very differently from the last one.

20 transforms to 4, and 4 is already the second chip of this very chain. The moment 4 reappears in seen, the loop stops and returns false — the chain is cycling (4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...) and can never reach 1.

Complexity: a number with d digits transforms into a value with at most 9² · d — a number close to its original digit count — so the sequence of distinct values before a repeat is bounded and, for any 32-bit n, converges in a small constant number of steps in practice; expressed asymptotically in n this is O(log n) time and space (each transform costs O(log n) to process the digits, and the set holds O(log n) distinct intermediate values before a repeat is forced).

Floyd's Cycle Detection (Slow/Fast Pointers)

OptimalTime O(log n)Space O(1)

Treat the sequence of transforms as a linked list where each value points to its digit-square-sum successor — exactly the shape Floyd’s cycle detection is built for. A slow pointer advances one step at a time, a fast pointer advances two steps at a time; if there is a cycle, the fast pointer eventually laps the slow one and they become equal at some value other than (or including) 1. If that meeting value is 1, n is happy.

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_num(x: int) -> int:
            return sum(int(d) ** 2 for d in str(x))

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

Correctness: if the sequence reaches 1, fast (which moves twice as fast) gets there first and the loop exits with fast == 1. If the sequence instead loops in a cycle that excludes 1, the fast pointer is confined to that same finite cycle and must eventually coincide with the slow pointer — the classic tortoise-and-hare guarantee.

Complexity: same bound on the number of distinct values before a repeat as the hash-set version → O(log n) time, but no set is kept — only two integer pointers → O(1) space.