Happy Number - Leetcode Solution

The Happy Number problem on Leetcode is a classic problem that can be solved using various techniques such as a hash set or Floyd's Cycle Detection Algorithm.

Problem:

Write an algorithm to determine if a number n is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

Input: 19 Output: true Explanation: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

Solution:

We can solve the Happy Number problem using the Floyd's Cycle Detection Algorithm (also known as Tortoise and Hare Algorithm), which is an efficient and widely used algorithm to detect and find cycles in a linked list.

The idea of the algorithm is to use two pointers - slow and fast, which move through the linked list at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the linked list has a cycle, then the two pointers will eventually meet at some point.

We can use the same algorithm to detect a cycle in the sequence of numbers generated by repeatedly calculating the sum of the squares of the digits of a number until the number becomes 1 or we detect a cycle. We can use a hash set to store the numbers that we have already seen, and if we encounter a number that is already in the hash set, then we know that we have detected a cycle.

Here is the step-by-step algorithm to solve the Happy Number problem:

1. Initialize a hash set to store the numbers that we have already seen.

2. Create a loop that iteratively calculates the sum of the squares of the digits of the current number and checks if it is equal to 1. If it is, then return True as the number is happy. If it is not, then add the current number to the hash set.

3. If we encounter a number that is already in the hash set, then we know that we have detected a cycle and the number is not happy. Return False.

Here is the Python code implementation using Floyd's Cycle Detection Algorithm:

class Solution:
    def sum_of_squares(self, n: int) -> int:
        # calculates the sum of the squares of digits of n
        sum = 0
        while n > 0:
            digit = n % 10
            sum += digit * digit
            n //= 10
        return sum
    
    def isHappy(self, n: int) -> bool:
        # initialize a hash set
        seen = set()
        
        # iterate until we find the happy number or a cycle
        while n != 1:
            # calculate the sum of the squares of digits of n
            n = self.sum_of_squares(n)
            
            # check if we have already seen this number
            if n in seen:
                return False
            
            # add the current number to the hash set
            seen.add(n)
        
        # if we reached here, then n is a happy number
        return True

Running Time Complexity:

The time complexity of the above algorithm is O(k * log n), where k is the number of iterations required to find the happy number or to detect a cycle in the sequence of numbers generated by repeatedly calculating the sum of the squares of the digits of a number, and log n is the time required to calculate the sum of the squares of the digits of a number. In the worst case, k can be as high as log n, which gives us a total time complexity of O(log^2 n).

Space Complexity:

The space complexity of the above algorithm is O(log n), as we are using a hash set to store the numbers that we have already seen. In the worst case, the hash set may contain all the numbers from the sequence generated by repeatedly calculating the sum of the squares of the digits of a number, which gives us a space complexity of O(log n).

1