Example 1
ready- Input
n = 19- Expected
true- Why
- 19 reaches 1 after following its digit-square sums
Happy Number
25 min · isHappy()A number can chase its own digits into one of two endings: it reaches 1, or it gets
trapped revisiting the same values forever.
Given a positive integer n, repeatedly replace it with the sum of the squares of its
digits. Return true if this process eventually reaches 1; otherwise return false.
A number that reaches 1 is called happy. Once a value repeats, every value after
it must repeat too, so the process can never escape to 1.
A few ground rules:
- Use every decimal digit, including zeros inside the number.
- Stop as soon as you reach
1or prove that the values are repeating. - The input is always a positive signed 32-bit integer—a whole number within
-2^31through2^31 - 1.
Constraints
1 <= n <= 2^31 - 1
Hints
Write the transformation first
Pop one digit with remainder % 10, square it, and add it to a running sum. Then
discard that digit with integer division by 10.
How do you prove forever?
There are only finitely many values the process can visit after its first step. If you keep a set of values you've already seen, a repeat proves you're in a loop.
Can two runners expose the loop?
Move one value through one transformation at a time and another through two. If there's a loop, the faster one must eventually catch the slower one.
Follow-up
Can you detect the repeating loop without storing every value you've visited?
Visible cases
Examples
Example 2
ready- Input
n = 2- Expected
false- Why
- 2 eventually enters a repeating cycle that excludes 1
Example 3
ready- Input
n = 1- Expected
true- Why
- 1 has already reached the happy ending
Interview signal
Asked at
AmazonGoogle
Remember every value
Start with the clearest proof. A seen set is a set containing every transformed
value you've already visited. If the current value is already there, the process has
entered a cycle—a chain that eventually returns to an earlier value—and will never
reach 1.
def digit_square_sum(value: int) -> int:
total = 0
while value > 0:
digit = value % 10
total += digit * digit
value //= 10
return total
def is_happy(n: int) -> bool:
seen: set[int] = set()
while n != 1 and n not in seen:
seen.add(n)
n = digit_square_sum(n)
return n == 1The first transformation reads every digit. After that, even the largest allowed input falls into a small range, so the remaining walk is bounded.
Time O(log n) to process the decimal digits and follow the bounded chain. Space O(log n) for the values recorded in the set.
Floyd's cycle detection — let a fast value catch a slow one
Floyd's cycle detection is a constant-space method that sends one runner one step
at a time and another runner two steps at a time. If the transformation enters a
cycle, the fast runner eventually catches the slow runner. If the fast runner reaches
1, the number is happy.
def digit_square_sum(value: int) -> int:
total = 0
while value > 0:
digit = value % 10
total += digit * digit
value //= 10
return total
def is_happy(n: int) -> bool:
slow = digit_square_sum(n)
fast = digit_square_sum(digit_square_sum(n))
while fast != 1 and slow != fast:
slow = digit_square_sum(slow)
fast = digit_square_sum(digit_square_sum(fast))
return fast == 1You don't need to know where the cycle starts. A collision anywhere inside it is enough
to prove that 1 isn't reachable.
Time O(log n) for the digit work and bounded cycle walk. Space O(1) because the two runners replace the set.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite