Solution For Happy Number

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).

Step by Step Implementation For Happy Number

class Solution {
    public boolean isHappy(int n) {
        Set seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}

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.

def isHappy(n):
    seen = set()
    while n not in seen:
        seen.add(n)
        n = sum(int(i)**2 for i in str(n))
    return n == 1

// 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.

var isHappy = function(n) {
    // keep track of seen numbers to prevent infinite loop
    var seen = {};
    
    // while n is not 1 and we have not seen it before
    while (n !== 1 && !seen[n]) {
        // add n to seen
        seen[n] = true;
        
        // calculate sum of squares of digits
        var sum = 0;
        while (n > 0) {
            var digit = n % 10;
            sum += digit * digit;
            n = Math.floor(n / 10);
        }
        
        // set n to sum
        n = sum;
    }
    
    // return true if n is 1, false otherwise
    return n === 1;
};

class Solution {
public:
    bool isHappy(int n) {
        // initialize a set to store seen numbers
        unordered_set seen;
        
        // while n is not 1 and n has not been seen before
        while (n != 1 && seen.find(n) == seen.end()) {
            // add n to seen
            seen.insert(n);
            
            // initialize sum to 0
            int sum = 0;
            
            // while n is not 0
            while (n != 0) {
                // get the last digit of n
                int digit = n % 10;
                
                // add the square of the digit to the sum
                sum += digit * digit;
                
                // remove the last digit of n
                n /= 10;
            }
            
            // set n to the sum
            n = sum;
        }
        
        // return true if n is 1, false otherwise
        return n == 1;
    }
};

//Solution for happy number problem in C# 

public class Solution {
    public bool IsHappy(int n) {
        
        //Create a hashset to store seen numbers
        HashSet seen = new HashSet();
        
        //While loop to iterate until a 1 is found or an infinite loop is detected
        while(n != 1 && !seen.Contains(n)){
            
            //Add the current number to the hashset
            seen.Add(n);
            
            //Create a variable to store the sum of the squares of the digits
            int sum = 0;
            
            //While loop to sum the squares of the digits
            while(n > 0){
                int digit = n % 10;
                sum += digit * digit;
                n /= 10;
            }
            
            //Set n equal to the sum
            n = sum;
        }
        
        //If n is 1, return true. Otherwise, return false.
        return n == 1;
    }
}