Happy Number easy

Problem Statement

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

A happy number is a number defined by the following process:

1. Starting with any positive integer, replace the number by the sum of the squares of its digits.
2. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
3. 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. Initialize a Set: Create a Set to store the numbers encountered during the process. This will help detect cycles.
2. Iterate until 1 or cycle is detected: While the number n is not 1 and not already in the seen set:
   • Calculate the sum of the squares of its digits.
   • Add the current number n to the seen set.
   • Update n with the newly calculated sum.
3. Return the result: If n is 1, return true (happy number). Otherwise, return false (unhappy number).

Explanation

The algorithm uses a Set to efficiently detect cycles. If a number repeats itself during the process, it means the number will loop endlessly without reaching 1, indicating an unhappy number. The Set provides constant time (O(1)) for checking if a number has already been seen. The algorithm terminates when either 1 is reached (happy number) or a cycle is detected (unhappy number).

Code (TypeScript)

function isHappy(n: number): boolean {
    const seen = new Set();

    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = sumOfSquaresOfDigits(n);
    }

    return n === 1;
}


function sumOfSquaresOfDigits(n: number): number {
    let sum = 0;
    while (n > 0) {
        const digit = n % 10;
        sum += digit * digit;
        n = Math.floor(n / 10);
    }
    return sum;
}


//Example usage
console.log(isHappy(19)); //true
console.log(isHappy(2));  //false

Complexity

• Time Complexity: O(log n) - In the worst case, the number of iterations is logarithmic to the input number. This is because the sum of squares of digits generally decreases with each iteration. However, in extremely rare cases, the sequence could be longer, but it's still considered to be bounded by a logarithmic function.

• Space Complexity: O(log n) - The space used by the seen set is proportional to the number of iterations, which is again, at most logarithmic with respect to the input number.