Problem
Determine if a number is “happy”. Replace it by the sum of squares of its digits, repeat. If it reaches 1, it’s happy. If it loops, it isn’t.
Example
Input: 19
Output: true
1²+9²=82, 8²+2²=68, 6²+8²=100, 1²+0²+0²=1.Solution
Floyd’s cycle detection. Use slow and fast pointers. If they meet at 1, it’s happy. Otherwise, it loops.
def is_happy(n):
def square_sum(x):
total = 0
while x:
total += (x % 10) ** 2
x //= 10
return total
slow = n
fast = square_sum(n)
while fast != 1 and slow != fast:
slow = square_sum(slow)
fast = square_sum(square_sum(fast))
return fast == 1function isHappy(n) {
function squareSum(x) {
let total = 0;
while (x) {
total += (x % 10) ** 2;
x = Math.floor(x / 10);
}
return total;
}
let slow = n, fast = squareSum(n);
while (fast !== 1 && slow !== fast) {
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
}
return fast === 1;
}int squareSum(int x) {
int total = 0;
while (x) { total += (x % 10) * (x % 10); x /= 10; }
return total;
}
bool isHappy(int n) {
int slow = n, fast = squareSum(n);
while (fast != 1 && slow != fast) {
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
}
return fast == 1;
}private int squareSum(int x) {
int total = 0;
while (x > 0) { total += (x % 10) * (x % 10); x /= 10; }
return total;
}
public boolean isHappy(int n) {
int slow = n, fast = squareSum(n);
while (fast != 1 && slow != fast) {
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
}
return fast == 1;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
The sequence either reaches 1 or enters a cycle. Floyd’s cycle detection finds either case efficiently with O(1) space.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?