Sponsored
Sponsored
The idea is to use a HashSet to track all numbers we've seen so far. If we encounter a number that we've seen before, it means we're in a cycle and the number is not happy. We keep replacing the number with the sum of the squares of its digits until we either reach 1 or the number starts repeating.
Time Complexity: O(log n), where n is the input number. Space Complexity: O(log n), as we store seen numbers.
1import java.util.HashSet;
2
3class Solution {
4 public boolean isHappy(int n) {
5 HashSet<Integer> seen = new HashSet<>();
6 while (n != 1 && !seen.contains(n)) {
7 seen.add(n);
8 n = getNext(n);
9 }
10 return n == 1;
11 }
12
13 private int getNext(int n) {
14 int totalSum = 0;
15 while (n > 0) {
16 int d = n % 10;
17 n /= 10;
18 totalSum += d * d;
19 }
20 return totalSum;
21 }
22}We use a HashSet to keep track of all seen numbers. The function getNext is responsible for calculating the sum of the squares of digits. If a number repeats, it indicates a cycle.
This approach utilizes Floyd's Cycle-Finding Algorithm (also known as Tortoise and Hare). Instead of using a hash set, we can use two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, whereas the fast pointer moves two steps at a time. If they meet, it means the sequence is cyclic.
Time Complexity: O(log n). Space Complexity: O(1), since no extra space is used apart from variables.
1 public bool IsHappy(int n) {
int slow = n, fast = GetNext(n);
while (fast != 1 && slow != fast) {
slow = GetNext(slow);
fast = GetNext(GetNext(fast));
}
return fast == 1;
}
private int GetNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}C# solution implements the cycle detection technique using two pointers. Slow pointer moves gradually, fast pointer leaps two steps. Their alignment indicates a loop unless 1 interrupts.