The problem
Replace a number by the sum of the squares of its digits, again and again. It is happy if this eventually reaches 1. Return whether n is happy.
Examples
- Input
n = 19
- Output
true
- Input
n = 2
- Output
false
Constraints
- 1 ≤ n ≤ 2³¹ − 1
The idea
19 is happy: 1² + 9² = 82, then 64 + 4 = 68, then 36 + 64 = 100, then 1. A number that is not happy loops forever instead — and it must loop: any number with 4 or more digits drops to something smaller, so the sequence is soon trapped below 1000, where only finitely many values exist.
Detecting that loop is Linked List Cycle again: Floyd’s tortoise and hare. One walker takes one step at a time and the other two; if there is a loop they meet, and if the sequence reaches 1 the fast one gets there first. No set of seen numbers is needed.
- Time
- O(log n) per step, and a bounded number of steps
- Space
- O(1)
Solution · every language run against every case
class Solution: def isHappy(self, n: int) -> bool: def step(x): # the sum of the squares of x's digits total = 0 while x: x, d = divmod(x, 10) total += d * d return total # The numbers either reach 1 or fall into a loop. Floyd's tortoise and hare finds out # without remembering them: fast moves two steps for each one of slow. slow, fast = n, step(n) while fast != 1 and slow != fast: slow, fast = step(slow), step(step(fast)) return fast == 1