Happy Number easy

Problem Statement

Write an algorithm to determine if a number 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.

Example 1:

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

Example 2:

Input: n = 2 Output: false

Steps

1. Initialization: Create a HashSet to store the numbers encountered during the process. This set will help detect cycles.
2. Iteration: While the number n is not 1 and has not been encountered before (not in the HashSet):
   • Calculate the sum of the squares of its digits.
   • Add the current number n to the HashSet.
   • Update n with the calculated sum.
3. Result: If n becomes 1, return true (happy number). Otherwise, return false (unhappy number, it entered a cycle).

Explanation

The algorithm uses a HashSet to efficiently detect cycles. If a number repeats during the process, it means the number will loop endlessly without reaching 1, hence it's not a happy number. The HashSet provides constant-time (O(1)) lookups, making the cycle detection very fast. The algorithm terminates when either 1 is reached or a cycle is detected.

Code

import java.util.HashSet;
import java.util.Set;

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

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

Complexity

• Time Complexity: O(log n). The number of iterations is roughly logarithmic because the number of digits decreases as the number gets smaller. Each iteration involves a constant number of operations to calculate the sum of squares. However, in worst case scenarios, it might take longer to hit a cycle.
• Space Complexity: O(log n). The HashSet can store at most O(log n) distinct numbers, where n is the input number. The space used is proportional to the number of digits in the input number.