Easy Cycle Detection Math & Geometry
In plain English: Keep replacing a number with the sum of the squares of its digits. It's happy if you eventually reach 1.
The sequence either converges to 1 or enters a cycle. Use Floyd's cycle detection (slow/fast pointers) or a hash set to detect the cycle. If you hit 1, it's happy.
Prompt
Write an algorithm to determine if a number n is happy. A happy number is defined by repeatedly summing the squares of its digits until you reach 1 or loop endlessly.
Try to write it from scratch before scrolling down.
Solution
def is_happy(n):
def digit_sq_sum(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
# Floyd's cycle detection: fast moves 2 steps, slow 1
slow = n
fast = digit_sq_sum(n)
while fast != 1 and slow != fast:
slow = digit_sq_sum(slow)
fast = digit_sq_sum(digit_sq_sum(fast)) # two steps so it laps slow if a cycle exists
return fast == 1
# Test: is_happy(19) == True (19->82->68->100->1)
# Test: is_happy(2) == False