Problem
Write an algorithm to determine whether a given integer n is a happy number.A number is considered happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. If the process enters a cycle that does not include 1, the number is not happy.
Example
Consider the following example to understand the expected input and output.Input
n = 19Output
true19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1Solution
There are two common approaches to solve the Happy Number problem. Both approaches use the same digit manipulation logic to calculate the sum of the squares of the digits, but they use different techniques to detect a cycle.Approach 1: Fast and Slow Pointers
This approach uses the Fast and Slow Pointer technique to detect a cycle. The process of calculating the sum of the squares of the digits can either eventually reach 1 or enter a cycle.This approach avoids using an additional HashSet to store previously seen numbers.
public boolean isHappy(int n) {
int slow = n;
int fast = n;
do {
slow = sumOfSquare(slow);
fast = sumOfSquare(sumOfSquare(fast));
} while (slow != fast);
return slow == 1;
}
private int sumOfSquare(int n) {
int number = 0;
while (n > 0) {
int digit = n % 10;
number += digit * digit;
n /= 10;
}
return number;
}Approach 2: HashSet and Cycle Detection
The second approach uses a HashSet to keep track of numbers that have already been encountered. If the same number appears again, it means the sequence has entered a cycle and the number is not happy.If the calculated value becomes 1, the number is happy.
Set<Integer> set = new HashSet<>();
public boolean isHappy(int n) {
if (n == 1) {
return true;
}
int number = 0;
while (n > 0) {
int digit = n % 10;
number += digit * digit;
n /= 10;
}
if (set.contains(number)) {
return false;
}
set.add(number);
return isHappy(number);
}Complexity
Each iteration calculates the sum of the squares of the digits, which takes O(log n) time for a number with log n digits.For the Fast and Slow Pointer approach, only the slow and fast variables are used for cycle detection, resulting in O(1) extra space.
For the HashSet approach, previously visited numbers are stored in a set, resulting in O(k) extra space, where k is the number of values encountered before reaching 1 or detecting a cycle.
