1. Happy Number (LeetCode)
Model answer
The task
Determine whether repeatedly replacing a positive integer with the sum of the squares of its digits eventually reaches 1. If the sequence loops without reaching 1, the number is not happy.
Key idea
The digit transformation is deterministic, so the sequence either reaches 1 or eventually repeats a value. Floyd’s cycle-finding algorithm detects a repeat using two pointers and constant extra space.
Approach
- Define a helper that computes the sum of the squared digits of a number.
- Start a slow pointer at the input and a fast pointer one transformation ahead.
- Advance the slow pointer once and the fast pointer twice per iteration.
- Stop if the fast pointer reaches 1 or the pointers meet.
- Return whether the fast pointer reached 1.
class Solution:
def isHappy(self, n: int) -> bool:
def next_value(value: int) -> int:
total = 0
while value > 0:
digit = value % 10
total += digit * digit
value //= 10
return total
slow = n
fast = next_value(n)
while fast != 1 and slow != fast:
slow = next_value(slow)
fast = next_value(next_value(fast))
return fast == 1
Complexity:
- Time: O(log n), since digit transformations rapidly reduce the value and each transformation processes its digits.
- Space: O(1), because only two pointers and a few temporary values are used.
Common follow-ups
- How can a set solve this? Store values as they appear; a repeated value proves a cycle, using O(k) extra space for k visited values.
- What if the transformation changes? The cycle-detection method still works for any deterministic transformation.
- How would you test edge cases? Check 1, a known happy value, and values whose sequences enter a non-1 cycle.