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.
1class
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.