DSA problem
Happy Number
Write an algorithm to determine if a number n is happy. A happy number is defined by the following process: starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat until the number equals 1 (the number is happy) or until it loops endlessly in a cycle that never reaches 1 (the number is not happy). Return true if n is a happy number and false otherwise.
At first glance this looks like a number-theory problem, but it is secretly a cycle-detection problem on an implicit "linked list". Each integer x has a single successor: the sum of the squares of its digits. Following successors traces out a sequence n → f(n) → f(f(n)) → ... that behaves exactly like walking pointers in a linked list. Either the sequence reaches 1 and stays there (happy), or it enters a cycle that does not contain 1 (unhappy).
A common but space-heavy solution stores every number seen in a hash set and returns false the moment a repeat appears. That works, but it can grow without a tight bound and adds overhead.
The optimal approach uses Floyd's tortoise-and-hare cycle detection directly on this sequence. The slow pointer advances by one squared-digit-sum per iteration; the fast pointer advances by two. If the sequence reaches 1, the fast pointer hits 1 first and we return true. Otherwise, because the sequence must eventually cycle (the values are bounded, so the pigeon-hole principle guarantees a repeat), slow and fast will meet at some value other than 1 — and that meeting tells us n is not happy. The algorithm uses only two integer variables, so it runs in O(log n) time and O(1) space.
Examples
n = 19truen = 2falsen = 1trueConstraints
- 1 <= n <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.