Happy Number LeetCode 202 Deep Dive

LeetCode 202 Happy Number defines a process: start with any positive integer, repeatedly replace it with the sum of the squares of its digits. If this process eventually reaches 1 and stays there, the number is "happy." If it never reaches 1 and instead loops endlessly, the number is "unhappy" (also called sad). Your task is to determine which case applies for a given input n.

For example, 19 is a happy number: 1² + 9² = 82, then 8² + 2² = 68, then 6² + 8² = 100, then 1² + 0² + 0² = 1. Reached 1 — happy. For 4: 4² = 16, 1² + 6² = 37, 3² + 7² = 58, 5² + 8² = 89, 8² + 9² = 145, 1² + 4² + 5² = 42, 4² + 2² = 20, 2² + 0² = 4. Back to 4 — a cycle with no 1 — unhappy.

The problem at its core is: detect whether a sequence eventually reaches a fixed point (1) or enters a cycle (not containing 1). This is exactly the structure that cycle detection algorithms are designed for, making Happy Number a textbook application of Floyd's tortoise-and-hare algorithm — or a simpler HashSet-based approach.

The most intuitive solution uses a HashSet (set in Python, HashSet in Java) to track every value the sequence visits. At each step, compute getNext(n). If the result is 1, return true immediately — n is happy. If the result is already in the set, we have detected a cycle that does not contain 1, so return false. Otherwise, add the result to the set and continue.

The time complexity is O(log n) per step because computing the digit-square-sum of a k-digit number takes O(k) = O(log n) work. The number of distinct values the sequence can visit before repeating is bounded (explained below), so the total number of steps is O(1) in terms of growth relative to n. Space complexity is O(log n) for the set of visited values — in practice very small since cycles are short.

The HashSet approach is clear, easy to implement, and easy to reason about. For most interview settings it is the preferred first answer. Its only downside is the O(log n) extra space for the visited set — which Floyd's algorithm eliminates entirely.

Floyd's cycle detection (tortoise-and-hare) eliminates the HashSet entirely by using two pointers that move through the sequence at different speeds. The slow pointer (tortoise) advances one step at a time: slow = getNext(slow). The fast pointer (hare) advances two steps at a time: fast = getNext(getNext(fast)). Both start at n.

If the sequence reaches 1, the fast pointer will arrive at 1 first (or simultaneously with slow). Since getNext(1) = 1, both pointers will then be stuck at 1 forever — they will meet at 1. If the sequence enters a cycle not containing 1, the fast pointer laps the slow pointer inside the cycle, and they meet at some value that is not 1. The meeting condition is fast == slow; the value at meeting determines happy or not.

Floyd's algorithm runs in O(log n) time per step with O(1) space — no HashSet needed. The implementation requires only a getNext helper function and a while loop with the two-pointer update. It is slightly less intuitive than the HashSet approach but demonstrates mastery of the tortoise-and-hare pattern beyond linked lists.

The digit-square-sum function maps positive integers to positive integers. Because every sequence is bounded (any large n maps to a much smaller value, and below ~1000 there are only ~1000 states), the sequence must eventually visit a state it has seen before. That is the definition of entering a cycle. There are exactly two possible outcomes: the cycle contains 1, or it does not.

This is precisely the abstract structure of the linked list cycle detection problem: a function f maps each node to the next node; the sequence x, f(x), f(f(x)), ... either leads to a terminal node (null / value 1) or loops. Floyd's algorithm detects the loop in O(1) space regardless of the domain — it works identically whether the "nodes" are list nodes or integers.

The key insight is that Happy Number is not fundamentally a math problem — it is a graph / sequence problem. Once you recognize that getNext defines a deterministic function from integers to integers and the sequence must eventually repeat, you immediately know cycle detection is the right tool. This pattern — applying Floyd's algorithm to a mathematical sequence — appears in several other interview problems.

All positive integers eventually reach one of two fates: they land on 1 (and stay there since getNext(1) = 1²= 1), or they enter the unhappy cycle 4→16→37→58→89→145→42→20→4. These are the only two attractors for the digit-square-sum function. Every positive integer eventually falls into one of them — there are no other cycles.

This means you can simplify both the HashSet and Floyd's approaches with a small optimization: instead of checking for any repeated value, just check if the sequence reaches 1 OR reaches 4 (the entry point of the unhappy cycle). If it reaches 1 first, it's happy; if it reaches 4 first, it's unhappy. This turns the problem into a simple while loop with two termination conditions.

The mathematical proof that these are the only two attractors relies on exhaustive computation for the range [1, 1000] combined with the bounding argument (all numbers > 1000 map to something ≤ 1000). In an interview, knowing the cycle 4→16→...→4 exists and checking for 4 as a termination condition is a concise, impressive alternative to the full HashSet or Floyd's implementation.

Python HashSet: def isHappy(n): seen = set(); while n != 1: n = getNext(n); if n in seen: return False; seen.add(n); return True. The getNext helper: def getNext(n): total = 0; while n > 0: n, digit = divmod(n, 10); total += digit ** 2; return total. The divmod approach is clean and Pythonic. The while loop terminates because either n becomes 1 (return True) or repeats (return False).

Python Floyd's: def isHappy(n): slow, fast = n, getNext(n); while slow != fast: slow = getNext(slow); fast = getNext(getNext(fast)); return slow == 1. Just three lines after defining getNext. Initialize fast one step ahead of slow (to avoid immediately meeting at n), run until they converge, then check if the meeting point is 1. Java is identical in structure: use a while(slow != fast) loop with the same two updates.

Both solutions run in O(log n) time with the HashSet version using O(log n) space and Floyd's using O(1) space. For the constraints of LeetCode 202 (n up to 2^31), the sequence converges within at most a few hundred steps regardless of approach — the difference in speed is negligible. Choose HashSet for clarity in interviews, Floyd's to demonstrate advanced technique.

Linked List Cycle II (LeetCode 142) finds the exact node where a linked list cycle begins, using an extended form of Floyd's algorithm. After slow and fast meet, reset one pointer to head and advance both one step at a time — they meet again at the cycle start. The same two-pointer mechanics apply; the domain is nodes instead of integers.

Missing Number (LeetCode 268) and Find the Duplicate Number (LeetCode 287) both have cycle detection solutions. LeetCode 287 in particular is isomorphic to Happy Number: treat the array values as a function mapping index to next index, apply Floyd's algorithm to find the duplicate. Understanding Happy Number deeply makes LeetCode 287 trivial.

Counting Bits (LeetCode 338) and Number of 1 Bits (LeetCode 191) are related digit-manipulation problems that build the same intuition for working with individual digits via bit operations or modular arithmetic. The Happy Number getNext function is a direct application of digit extraction — mastering it strengthens your foundation for all digit-processing problems.