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: Start with the input number n.
2. Iteration: Repeatedly calculate the sum of the squares of the digits of the current number.
3. Check for 1: If the sum becomes 1, the number is happy, return true.
4. Check for Cycle: Maintain a HashSet to track seen numbers. If a number is encountered again, it indicates a cycle, and the number is not happy, return false.
5. Update: Update the current number with the sum of squares of its digits.
6. Repeat: Continue steps 2-5 until either step 3 or 4 is met.

Explanation:

The algorithm uses a HashSet to efficiently detect cycles. If a number is encountered more than once during the iterative process, it implies that the process will enter an infinite loop without reaching 1. The HashSet provides constant-time (O(1)) lookup for checking if a number has been seen before. This prevents unnecessary computations and improves efficiency.

Code:

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsHappy(int n) {
        HashSet<int> seen = new HashSet<int>(); 
        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 logarithmic because the number of digits generally decreases with each iteration. In the worst case, it might take a longer time, but the use of the HashSet prevents infinite loops.
• Space Complexity: O(log n). The HashSet can store at most O(log n) distinct numbers in the worst-case scenario. The space used is proportional to the number of digits in the input number.