Happy Number
Repeatedly replace a number by the sum of the squares of its digits, and decide whether the process reaches 1 or loops forever.
Open on LeetCode ↗Intuition
You will reach for a set — remember every number you have seen, and if one repeats, declare a cycle. That is correct, and it is also the answer that stops you from seeing what this problem is actually about. Look at the shape of the process: every number has exactly one successor, sumOfSquaredDigits(n), and no number ever has two. A structure where each node points to exactly one next node is a linked list — the pointers just happen to be computed rather than stored. And the question 'does this repeat?' is the question 'does this list have a cycle?', which Floyd's slow/fast solves in O(1) space instead of the set's O(k). Run one pointer at one hop per turn and another at two; if fast reaches 1, the number is happy, because 1 maps to itself and the chain is stuck there. If the two ever land on the same value, you are inside a loop that will never contain 1. That is the invariant — once both pointers are in the cycle, fast closes the gap by exactly one node per turn, so it cannot step over slow; it must eventually land on it.
The digit-square-sum function turns the integers into a functional graph, so iterating it must eventually cycle. Floyd's tortoise and hare detects that cycle in O(1) space — the same machinery as linked-list cycle detection, applied to a sequence with no list.
Approach
Recognise the sequence as a linked list
The transformation n to sumOfSquaredDigits(n) is a function: one input, one output, deterministic. That makes the sequence of values a chain of nodes with exactly one outgoing edge each. Because the digit-square sum of any number below 1000 is at most 243, the values are trapped in a finite range forever after the first step — and a finite chain where every node has a successor must eventually revisit a node. So there are only two possible endings: land on 1, or enter a cycle.
Race slow and fast instead of remembering everything
Set both pointers to n. Each turn advance slow by one application of the digit-square sum and fast by two. The set-based solution stores every value it has seen, which is O(k) memory; Floyd's stores two integers. If a cycle exists, both pointers are eventually inside it, and from then on fast gains exactly one node of ground per turn — so the gap shrinks to zero and they collide. There is no way for fast to skip past slow.
Read the meeting point, or the arrival at 1
Two exits. If fast ever hits 1, stop and return True — 1 squares to 1, so it is a self-loop and the chain can never leave. If slow and fast meet at any other value, that value sits on a cycle that does not contain 1, so the process runs forever and you return False. Checking fast for 1 rather than slow just gets you the answer sooner; either works.
Solution & live demo
Common pitfalls
Looping forever on an unhappy number
while n != 1:
n = nxt(n)if slow == fast:
return FalseUnhappy numbers enter a cycle that never contains 1, so the loop never exits. Detecting the repeat is the entire non-obvious part of the problem.
Checking only slow for 1
if slow == 1: return True
if fast == 1: return True
The fast pointer reaches 1 first, and once either pointer lands on 1 the sequence is fixed there. Testing the slow pointer still works but takes twice as long — and testing it instead of the meet condition risks ordering bugs.
Using a set of seen values
seen = set() while n not in seen:
slow, fast = n, n
Perfectly correct and often the expected answer — but it's O(k) space for the cycle length. Floyd's gets the same result with two integers, which is the version worth knowing.
Edge cases
Already happy — the fast pointer hits 1 on its first move (or the initial check catches it) and returns True.
Enters the well-known 4-16-37-58-89-145-42-20 cycle; slow and fast meet inside it and the answer is False.
Zero digits contribute 0 to the sum and are harmless — 100 gives 1 immediately.
After one step any input collapses below 1000, and below 244 after the next, so the search space is tiny regardless of how big n starts.