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.
1function isHappy(n) {
2 const getNext = (num) => {
3 return num.toString().split('').reduce((sum, digit) => sum + Math.pow(parseInt(digit), 2), 0);
4 };
5 const seen = new Set();
6 while (n !== 1 && !seen.has(n)) {
7 seen.add(n);
8 n = getNext(n);
9 }
10 return n === 1;
11}Here, we use a set to track encountered numbers. If a number is repeated, it's clear we are in a cycle. The getNext function computes the new number as the sum of the squares of the digits.
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
Python implementation uses two pointers to identify cycles. Slow is incremented one step at a time; fast takes two steps. A collision without achieving 1 confirms a cycle.