Happy Number

LeetCode 202: Happy Number Solution & Explanation

Problem Overview

TL;DR: We detect a cycle in the sequence of numbers generated by summing the squares of digits; if the cycle stabilizes at 1, the number is happy, otherwise, it is not.

The Happy Number problem asks us to determine the fate of a specific numerical process starting with a given integer n. In this process, we replace the current number with the sum of the squares of its digits. We repeat this indefinitely. There are two possible outcomes: either the process eventually reaches the number 1 (where it stays, as $1^2 = 1$), or it enters a cycle that does not include 1.

Our goal in the LeetCode 202 solution is to return true if n reaches 1, and false if it gets stuck in a loop. This is a classic interview question that tests the ability to recognize implicit data structures and cycle detection mechanisms.

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:

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.

Algorithm Strategy: Two Pointer Patterns

1. Helper Function: Implement a function getNext(number) that calculates the sum of the squares of the digits.
2. Initialization: Initialize two variables, slow and fast, both starting at the input n.
3. Traversal:
   • Advance slow by applying getNext once.
   • Advance fast by applying getNext twice.
4. Cycle Detection:
   • Continue this loop as long as fast is not 1 and slow is not equal to fast.
   • If fast becomes 1, the number is happy. Terminate and return true.
   • If slow equals fast (and neither is 1), we are trapped in a cycle. Terminate and return false.
5. Edge Case: Ensure the loop logic handles the initial state correctly (often done using a do-while loop or by initializing pointers to the first and second steps respectively).

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 = 100$, then $1^2 + 0^2 + 0^2 = 1$.
   • State: slow = 100, fast = 1.
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.

Pattern Reuse Notes

The Two Pointers - Fast & Slow pattern is a powerful tool for detecting cycles in linear data structures. It applies directly to:

• LeetCode 141: Linked List Cycle - The canonical application of this pattern. Detect if a linked list has a loop.
• LeetCode 287: Find the Duplicate Number - Uses cycle detection on an array interpreted as a linked list to find a duplicate.
• LeetCode 392: Is Subsequence - While primarily a standard Two Pointer approach, understanding pointer movement logic is shared across these problems.

Mastering LeetCode 202 solidifies your understanding of implicit graphs and cycle detection without auxiliary space.

Reference Implementation

C++ Solution for LeetCode 202

1class Solution {
2public:
3    // Helper function to calculate sum of squares of digits
4    int getNext(int n) {
5        int totalSum = 0;
6        while (n > 0) {
7            int d = n % 10;
8            n = n / 10;
9            totalSum += d * d;
10        }
11        return totalSum;
12    }
13
14    bool isHappy(int n) {
15        int slow = n;
16        int fast = getNext(n); // Advance fast one step ahead initially to start loop
17
18        // Continue until fast reaches 1 (happy) or fast meets slow (cycle)
19        while (fast != 1 && slow != fast) {
20            slow = getNext(slow);           // Move slow by 1 step
21            fast = getNext(getNext(fast));  // Move fast by 2 steps
22        }
23
24        return fast == 1;
25    }
26};

Java Solution for LeetCode 202

1class Solution {
2    // Helper function to calculate sum of squares of digits
3    private int getNext(int n) {
4        int totalSum = 0;
5        while (n > 0) {
6            int d = n % 10;
7            n = n / 10;
8            totalSum += d * d;
9        }
10        return totalSum;
11    }
12
13    public boolean isHappy(int n) {
14        int slow = n;
15        int fast = getNext(n);
16
17        // Standard Floyd's Cycle Detection logic
18        while (fast != 1 && slow != fast) {
19            slow = getNext(slow);
20            fast = getNext(getNext(fast));
21        }
22
23        return fast == 1;
24    }
25}

Python Solution for LeetCode 202

1class Solution:
2    def isHappy(self, n: int) -> bool:
3        def get_next(number):
4            total_sum = 0
5            while number > 0:
6                number, digit = divmod(number, 10)
7                total_sum += digit ** 2
8            return total_sum
9
10        slow = n
11        fast = get_next(n)
12
13        # Loop until we find 1 or detect a cycle
14        while fast != 1 and slow != fast:
15            slow = get_next(slow)
16            fast = get_next(get_next(fast))
17
18        return fast == 1