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.
1bool isHappy(int n) {
2 int getNext(int n) {
3 int totalSum = 0;
4 while (n > 0) {
5 int d = n % 10;
6 n = n / 10;
7 totalSum += d * d;
8 }
9 return totalSum;
10 }
11
12 int seen[1000] = {0};
13 while (n != 1 && !seen[n]) {
14 seen[n] = 1;
15 n = getNext(n);
16 }
17 return n == 1;
18}We define a helper function getNext that calculates the sum of the squares of the digits. We use an integer array to track seen numbers. If a number repeats, it means a cycle has formed and thus it is not a happy number.
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
Java implementation of Floyd's cycle detection. The slow pointer goes step by step, while the fast pointer advances quickly. Meeting indicates a loop unless one hits 1.