Brute Force Approach for Happy Number

The most intuitive approach is to simulate the process and store every number we encounter in a data structure, such as a Hash Set.

1. Initialize an empty Hash Set seen.
2. Calculate the sum of the squares of the digits of n.
3. If the new n is 1, return true.
4. If the new n is already in seen, we have detected a cycle that is not 1. Return false.
5. Add the current n to seen and repeat.

Pseudo-code:

text
function isHappy(n):
    seen = new HashSet()
    while n != 1:
        if seen.contains(n):
            return false
        seen.add(n)
        n = sumOfSquares(n)
    return true

Why this approach is suboptimal: While this solution is correct, its Space Complexity is $O(M)$, where $M$ is the number of distinct integers in the sequence before a cycle is found. In a constrained environment or systems with limited memory, allocating a hash table to store history is unnecessary overhead when we only need to detect the existence of a cycle, not the full history.

Core Insight for Happy Number

The key insight for the optimal LeetCode 202 solution is to recognize that the sequence of numbers forms an implicit LinkedList structure.

Given a number $n$, the next number is strictly deterministic: $next(n) = \sum digits^2$. Because the transformation is deterministic, if we ever revisit a number, we are in a cycle.

Instead of storing the history, we can use two pointers moving at different speeds:

1. Slow Pointer: Computes the next number once per iteration ($n \to next(n)$).
2. Fast Pointer: Computes the next number twice per iteration ($n \to next(next(n))$).

The Invariant: If a cycle exists (which happens if the number is not happy), the Fast Pointer will eventually "lap" or catch up to the Slow Pointer within the cycle. If the number is happy, the Fast Pointer will reach the value 1.

Visual Description: Imagine a graph where every node has exactly one outgoing edge pointing to the sum of the squares of its digits.

• If n is happy, the path looks like a straight line ending at a node with value 1, which loops to itself ($1 \to 1$).
• If n is not happy, the path leads into a closed loop of numbers (e.g., $4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4...$).
• The algorithm visualizes two markers traversing this graph. The fast marker jumps two nodes for every single jump of the slow marker. They are guaranteed to collide.

Execution Flow

Let's trace n = 19 (Happy Case):

1. Start: slow = 19, fast = 19.
2. Step 1:
   • slow moves to $1^2 + 9^2 = 82$.
   • fast moves to $82$, then $8^2 + 2^2 = 68$.
   • State: slow = 82, fast = 68. No collision.
3. Step 2:
   • slow moves to $6^2 + 8^2 = 100$.
   • fast moves to $6^2+8^2$, then .
4. Check: fast is 1. The loop terminates. Return true.

Let's trace n = 2 (Unhappy Case):

1. Start: slow = 2, fast = 2.
2. Step 1:
   • slow becomes 4.
   • fast becomes 4, then 16.
3. Step 2:
   • slow becomes 16.
   • fast becomes $1^2+6^2=37$, then $3^2+7^2=58$.
4. ... The process continues.
5. Eventually, slow enters the cycle $4 \to 16 \to 37 \dots$ and fast is already circulating inside it.
6. Since fast moves faster, it will eventually land on the same number as slow.
7. Check: slow == fast (and not 1). Return false.

Proof of Correctness

Termination: One might ask: "Will the numbers grow infinitely?" No. Consider the maximum next value. For a 3-digit number (max 999), the max sum of squares is $9^2 + 9^2 + 9^2 = 243$. For a 4-digit number (max 9999), the max sum is $4 \times 81 = 324$. For any number $n \geq 1000$, the sum of the squares of its digits is strictly less than $n$. Therefore, the sequence must eventually fall below 1000 (specifically below 163). Once in this bounded range, by the Pigeonhole Principle, the sequence must either reach 1 or repeat a number (form a cycle).

Cycle Detection: Floyd’s Cycle-Finding Algorithm guarantees that if a cycle exists, the fast and slow pointers will meet. Since the sequence is deterministic and bounded, a collision is inevitable if 1 is not reached.

Reference Implementation

C++ Solution for LeetCode 202

cpp
class Solution {
public:
    // Helper function to calculate sum of squares of digits
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = getNext(n); // Advance fast one step ahead initially to start loop

        // Continue until fast reaches 1 (happy) or fast meets slow (cycle)
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);           // Move slow by 1 step
            fast = getNext(getNext(fast));  // Move fast by 2 steps
        }

        return fast == 1;
    }
};

Java Solution for LeetCode 202

java
class Solution {
    // Helper function to calculate sum of squares of digits
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);

        // Standard Floyd's Cycle Detection logic
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }

        return fast == 1;
    }
}

Python Solution for LeetCode 202

python
class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2
            return total_sum

        slow = n
        fast = get_next(n)

        # Loop until we find 1 or detect a cycle
        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))

        return fast == 1