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.
1#include <unordered_set>
2
3bool isHappy(int n) {
4 auto getNext = [](int n) {
5 int totalSum = 0;
6 while (n > 0) {
7 int d = n % 10;
8 n /= 10;
9 totalSum += d * d;
10 }
11 return totalSum;
12 };
13 std::unordered_set<int> seen;
14 while (n != 1 && seen.find(n) == seen.end()) {
15 seen.insert(n);
16 n = getNext(n);
17 }
18 return n == 1;
19}The unordered_set is used to keep track of all previously seen numbers. If we encounter a number that we have seen before, it means we are in a cycle. We repeatedly replace the number with the sum of the squares of its digits until we reach 1 or a cycle is detected.
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.
1JavaScript solution utilizing fast and slow pointer technique to find cycles efficiently without additional space apart from variables.