Happy Number — Cycle Detection With a HashSet at FAANG

Problem Statement#

A happy number repeatedly replaces itself by the sum of squares of its digits. If the process eventually reaches 1, return true; if it loops endlessly, return false.

Constraints:

• 1 <= n <= 2^31 - 1

Input:  n = 19
Output: true
Trace:  19 -> 82 -> 68 -> 100 -> 1

Input:  n = 2
Output: false
Trace:  2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 (cycle)

Why This Problem Matters#

LeetCode 202 Happy Number is a frequent FAANG hashmap interview warm-up at Amazon, Microsoft, Google, and Meta. The interview signal is whether you spot that the process either reaches 1 or revisits a value (cycle), and that a HashSet is the simplest cycle detector.

The HashSet cycle pattern reappears in Linked List Cycle (LC 141), graph cycle detection, and de-duplication in event streams. Hash table FAANG fluency includes knowing the Floyd tortoise-and-hare alternative that achieves O(1) extra space.

The mathematical fact (digit-square chains for inputs in 32-bit range stay below ~700) makes this a deceptively bounded problem despite the unbounded-looking iteration count.

The Core Insight#

Define next(n) = sum of squares of digits. Iterate until either n == 1 (happy) or you revisit a previous value (cycle). A HashSet of seen values is the natural cycle detector. The chain is bounded because for 32-bit n, digit squares cap the next value at ~243 per digit times 10 digits, then quickly compress.

For O(1) space, run two pointers: slow = next(slow) and fast = next(next(fast)). If they meet at 1, happy. If they meet anywhere else, cycle.

Visual Dry Run#

Input n = 19:

Return true.

Solution (Optimal)#

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_n(x: int) -> int:
            total = 0
            while x:
                d = x % 10
                total += d * d
                x //= 10
            return total
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = next_n(n)
        return n == 1

var isHappy = function(n) {
    const nextN = (x) => {
        let total = 0;
        while (x) {
            const d = x % 10;
            total += d * d;
            x = Math.floor(x / 10);
        }
        return total;
    };
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = nextN(n);
    }
    return n === 1;
};

Time: O(log n) per next_n step times bounded number of iterations. Space: O(log n) for the HashSet of seen values; O(1) with Floyd's two-pointer variant.

Common Mistakes#

• Iterating without a cycle guard, causing infinite loops on unhappy numbers.
• Using n in list_seen instead of HashSet — degrades to O(n) per check.
• Computing digits via string conversion when arithmetic is faster.
• Forgetting to add n to seen before stepping; can miss the immediate cycle on n = 4.
• Using float division in JavaScript (x / 10) without Math.floor.

Interview Tips#

• Mention both solutions: HashSet for clarity, Floyd's two-pointer for O(1) space.
• Justify why the chain is bounded for 32-bit inputs.
• Encapsulate next_n as a helper; it shows clean factoring.
• Avoid string conversion for digit extraction; arithmetic is preferred.

Follow-up Questions#

• Achieve O(1) space. (Hint: Floyd's tortoise-and-hare on the next function.)
• What is the longest possible chain for 32-bit n? (Hint: empirically below ~700 distinct values.)
• Generalize to base k. (Hint: digit extraction modulo k.)
• Prove unhappy numbers always reach the 4-16-37-58-89-145-42-20 cycle. (Hint: number-theoretic invariant.)
• How does this relate to Linked List Cycle (LC 141)? (Hint: same Floyd's algorithm on a function iterator.)

Key Takeaways#

• LeetCode 202 Happy Number is the canonical HashSet cycle detection FAANG warm-up.
• Iterate n -> next(n) until you reach 1 or revisit a value.
• HashSet gives O(1) cycle checks; total time is O(log n) per step.
• Floyd's tortoise-and-hare drops space to O(1) without losing correctness.
• Digit extraction via arithmetic (x % 10 and x //= 10) beats string conversion.
• All unhappy 32-bit numbers funnel into the 4-16-37-58-89-145-42-20 cycle.
• The same cycle-detection pattern reappears in Linked List Cycle and graph traversal.