Keep replacing a number with the sum of its digits squared. Either it reaches one or loops, and slow and fast pointers spot the loop.
▼The problem
LeetCode 202 (Easy). Repeatedly replace a positive integer n by the sum of the squares of its digits. n is happy if this reaches 1, and not happy if it loops forever without reaching 1.
Examples (LeetCode's): 19 → true (19 → 82 → 68 → 100 → 1) and 2 → false (2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, a loop).
The solution
def isHappy(n):
def nxt(x):
return sum(int(d) ** 2 for d in str(x))
slow, fast = n, nxt(n)
while fast != 1 and slow != fast:
slow = nxt(slow)
fast = nxt(nxt(fast))
return fast == 1Transcript
Happy Number. Replace a number with the sum of the squares of its digits, and keep going. If you reach one, it's happy. If you never do, it loops forever.
Take nineteen. One plus eighty-one is eighty-two. Sixty-four plus four is sixty-eight. Thirty-six plus sixty-four is one hundred. Then one. Happy! Take two. Four, sixteen, thirty-seven, fifty-eight, eighty-nine, one forty-five, forty-two, twenty, and back to four. A loop, so two is not happy.
The easy way: drop every number into a hash set. Stop on one, or on a repeat. It works, but the set keeps growing.
Here's the trick. Each number points to one next number, like a linked list. And it can't grow forever: a three-digit number maps to at most two hundred forty-three. So the chain either reaches one, or rides a loop, like a carousel. Two riders: slow moves one horse, fast moves two. On a loop, fast laps slow, and they meet.
In code, next sums the squared digits. Slow starts at n, fast one step ahead. While fast isn't one and they differ, slow steps once, fast steps twice. Return whether fast is one.
Try two. Slow on two, fast on four. Then four and thirty-seven. Sixteen and eighty-nine. Thirty-seven and forty-two. Fifty-eight and four. Eighty-nine and thirty-seven. One forty-five and eighty-nine. Both land on forty-two. They met, not on one: not happy.
The loop is caught within a lap, so it's about order log n time, and just two numbers, order one space.
One horse, two horses, catch the loop. That's Happy Number.