Lets Code Everyday - Day4

Question - 4 :-

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.

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

Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:
Input: n = 2
Output: false

First approach:

class Solution {
    public boolean isHappy(int n) {
         int sum = 0;
    while (n != 1 && n != 4) {
        while (n != 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        n = sum;
        sum = 0;
    }
    return n == 1;
    }
}

Here is a step by step explanation of how the code works:

1. The function isHappy takes an integer n as input and returns a boolean value.

2. The integer variable sum is initialized to 0.

3. The while loop checks if the input n is not equal to 1 and 4.

4. Inside the while loop, another while loop is used to calculate the sum of squares of the digits of the number n.

5. The integer variable digit is initialized to the remainder obtained by dividing n by 10 (gives us the last digit of the number).

6. The variable sum is updated by adding the square of digit to it.

7. The variable n is updated by dividing n by 10, which removes the last digit from n.

8. Steps 5-7 are repeated until n becomes 0.

9. The value of n is updated to the value of sum.

10. The value of sum is reset to 0.

11. Steps 4-10 are repeated until the value of n becomes either 1 or 4.

12. If the value of n is 1, the function returns true, indicating that the input n is a Happy Number.

13. If the value of n is 4, the function returns false, indicating that the input n is not a Happy Number.

14. The end result is a boolean value that tells us whether the input n is a Happy Number or not.

The time complexity of the code is O(k log k), where k is the number of digits in n.

The space complexity of the code is O(1), i.e., constant space, as only a constant amount of additional memory is required to store the variable sum. The memory used for storing n and digit is reused in each iteration of the while loop.

Second approach:

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n == 1;
    }

    private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}
}

Here is a step-by-step explanation of how the code works:

1. The function isHappy takes an integer n as input and returns a boolean value.

2. A new HashSet called seen is initialized to keep track of the numbers that have been seen during the computation.

3. The while loop checks if the input n is not equal to 1 and if n is not already present in the seen set.

4. Inside the while loop, the value of n is added to the seen set to mark it as seen.

5. The value of n is updated to the next number in the Happy Number sequence using the getNext method.

6. The getNext method calculates the sum of squares of the digits of the number n using the same approach as the previous code you provided.

7. The value of sum is returned from the getNext method.

8. Steps 5-7 are repeated until the value of n becomes either 1 or is already present in the seen set.

9. If the value of n is 1, the function returns true, indicating that the input n is a Happy Number.

10. The end result is a boolean value that tells us whether the input n is a Happy Number or not.

The time complexity of this code is also O(k), where k is the number of digits in n. The space complexity is O(k) as well, since the seen set can contain up to k elements in the worst-case scenario where every number in the Happy Number sequence is distinct.

However, this implementation might be more efficient in practice, since it can avoid unnecessary iterations if a cycle is detected in the Happy Number sequence.