LeetCode 202 – Happy Number

Happy Number is Linked List Cycle with the list replaced by a function. There are no nodes and no next pointer, and Floyd's algorithm works anyway — which is the point of the problem. Cycle detection needs a successor function, not a data structure.

The problem

Repeatedly replace a number by the sum of the squares of its digits. It is happy if this reaches 1; otherwise the process loops forever without reaching 1. Return whether n is happy.

19 -> 1² + 9²  = 82
   -> 8² + 2²  = 68
   -> 6² + 8²  = 100
   -> 1² + 0² + 0² = 1     happy

2  -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...   unhappy

The unhappy example is the whole problem: it enters a cycle that does not contain 1, and the naive loop never terminates.

Why it always terminates

The problem statement says the process "loops endlessly in a cycle", which is a claim worth being able to justify rather than accept.

For any three-digit number the digit-square sum is at most 3 × 81 = 243. So every number below 1000 maps below 1000, and any larger number shrinks — a four-digit number maps to at most 4 × 81 = 324. The sequence is therefore trapped in a finite set almost immediately, and a walk through a finite set must eventually repeat.

That is the whole argument, and it also tells you the third solution is viable: since the state space is small, a hash set of seen values is bounded, not unbounded.

Three solutions

The third deserves a word because it is tempting: there is exactly one non-trivial cycle in this process, so return n == 1 || n == 7 after a few steps, or checking membership of the known 8-element loop, passes every test. It is also unmaintainable and does not generalise to "sum of cubes" or any other variation. Mention it and reject it.

Floyd, with a function instead of a list

The sequence n → digitSquareSum(n) is a linked list where next(x) is computed rather than stored. Everything from problem 141 transfers unchanged: a slow pointer taking one step, a fast pointer taking two, and they meet if and only if there is a cycle.

The one difference: this "list" always has a cycle — either the self-loop at 1, or the other one. So the meeting point tells you which cycle you fell into, and the answer is whether they met at 1.

Java

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = next(n);

        // This sequence ALWAYS cycles, so the loop always ends. The question is
        // which cycle: the self-loop at 1, or the other one.
        while (fast != 1 && slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }

        return fast == 1;
    }

    /** The successor function: this is the "next pointer". */
    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

fast starts one step ahead so the loop condition is not immediately true — the same reason problem 141 compares after moving rather than before.

Checking fast != 1 rather than slow != 1 is deliberate: the fast pointer reaches 1 first, so testing it exits as early as possible. Testing both would be correct and redundant.

No overflow is possible. The digit-square sum of any int is at most 10 × 81 = 810, so the sequence collapses into a small range on the first step.

Python

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_value(x: int) -> int:
            total = 0
            while x > 0:
                x, digit = divmod(x, 10)
                total += digit * digit
            return total

        slow, fast = n, next_value(n)

        while fast != 1 and slow != fast:
            slow = next_value(slow)
            fast = next_value(next_value(fast))

        return fast == 1

divmod gives the quotient and remainder in one call, which is exactly the shape of digit extraction. sum(int(c) ** 2 for c in str(x)) is shorter and allocates a string per step — fine here, and worth naming as the trade rather than choosing silently.

The hash-set version, for comparison

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

Shorter, obviously correct, and O(log n) space — the set holds at most the few dozen values the sequence visits before repeating. Give this first. Floyd is the answer to "can you do it in constant space", not the answer to the question as asked.

Complexity

The log n is the digit count, which is what the first next call costs. After that the value is below 1000 and the remaining work is bounded by a constant — the cycle is at most 8 long and the tail is short. Quoting O(log n) is honest; quoting O(1) is nearly true and harder to defend.

The pattern

Floyd's algorithm applies to any deterministic successor function on a finite state space. 141 uses node.next, 142 finds where the cycle starts, and Find the Duplicate Number (287) uses i → nums[i] to find a repeated value in O(1) space. This one uses arithmetic.

The general recognition: if the state is finite and the next state is a function of the current one, you have a linked list whether or not anything is allocated.

What the interviewer is checking

• That you can argue the sequence must eventually repeat.
• That you give the hash set first, then meet the constant-space follow-up.
• That Floyd's algorithm needs a successor function, not nodes.
• That this sequence always cycles, so the loop always terminates.
• n = 1 and n = 7, the small happy numbers.
• That the digit-square sum cannot overflow.
• That hard-coding the known cycle is not an answer.