Foundation drill for this topic
Easy Cycle Detection
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) == FalseQuick recall drills to reinforce this pattern.
Digit-square-sum with cycle detection (fast/slow or set) determines happiness.
def digit_sq_sum(n):
s = 0
while n:
n, d = divmod(n, 10)
s += d * d
return sPhase 1: detect cycle with slow/fast. Phase 2: reset slow to head, advance both by 1 — they meet at cycle start.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # cycle start