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.
1def isHappy(n):
2 def get_next(number):
3 return sum(int(char) ** 2 for char in str(number))
4
5 seen = set()
6 while n != 1 and n not in seen:
7 seen.add(n)
8 n = get_next(n)
9 return n == 1In this solution, we use a Python set to track all numbers observed so far. If the number is already in the set, it means a cycle is detected. The helper function get_next computes 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.
1JavaScript solution utilizing fast and slow pointer technique to find cycles efficiently without additional space apart from variables.