Description
A positive integer is happy if repeatedly replacing it by the sum of its squared decimal digits eventually reaches 1. Otherwise the process cycles. Decide whether n is happy.
Solution
def is_happy(n):
def next_value(value):
total = 0
while value:
value, digit = divmod(value, 10)
total += digit * digit
return total
slow, fast = n, next_value(n)
while fast != 1 and slow != fast:
slow = next_value(slow)
fast = next_value(next_value(fast))
return fast == 1Examples
Example 1
- Input
[19]- Output
true
19 goes to 82, 68, 100, then 1.
Example 2
- Input
[2]- Output
false
The sequence repeats without reaching 1.
Example 3
- Input
[1]- Output
true
It is already at the target.
Approach
Treat the digit-square transformation as a next pointer. Advance a slow value once and a fast value twice until fast reaches 1 or both meet in a non-happy cycle.
Time & space
O(log n) time for the initial digit processing plus a bounded decimal-state cycle, and O(1) auxiliary space.