Happy Number
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.
- 1 <= n <= 2³¹ - 1
Intuition
For happy number 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
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(log n) time and O(1) space.
Recognise the sequence as a linked list
The map from n to the sum of its squared digits is deterministic: one input, one output. So the sequence is a chain where every node has exactly one outgoing edge. And since the digit-square sum of any number below 1000 is at most 243, the values are trapped in a finite range after the first step — a finite chain where every node has a successor must revisit one. Hence only two endings exist: reach 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.