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, and repeat the process until the number equals 1, or it loops endlessly in a cycle that does not include 1. Return true if n is a happy number, and false if not.
n = 19truen = 2falseslow = n, fast = getNext(n)fast ≠ 1 and slow ≠ fastslow = getNext(slow), fast = getNext(getNext(fast))fast == 1 → return true (happy!)slow == fast ≠ 1 → return false (cycle!)Every number maps deterministically to one successor via getNext. This creates an implicit linked list. For non-happy numbers, the sequence eventually revisits a value, forming a cycle. Floyd's algorithm detects any cycle in O(1) space — the fast pointer laps the slow pointer inside the cycle. For happy numbers, fast reaches 1 before any meeting occurs (since getNext(1) = 1, it loops at 1 forever).
You can store every number you see in a set and stop on a repeat. That uses extra memory.
The sequence behaves like a linked list, where next is the digit square sum. So use fast and slow pointers, exactly as in cycle detection. If fast reaches 1, the number is happy, and if they meet elsewhere, it is not.
Any repeated next function forms a linked list. Floyd detects the loop without a set.
Run the animation above on your own input, or watch the 1:12 video explanation of Happy Number with a dry run and Java code.