Happy number

XXX. Happy Number

Math

Hashing

Problem Statement:

Write an algorithm to determine if a number n is "happy".
A number is considered happy if, starting with any positive integer, replacing the number with the sum of the squares of its digits eventually reaches 1. If it loops endlessly in a cycle that does not include 1, it is not a happy number.

Algorithm:

1. Initialize a set to track numbers we have already seen (to detect cycles).
2. Repeat the process:
   • Calculate the sum of the squares of the digits of the current number.
   • If the result is already in the set, a cycle has been detected; return false.
   • Add the result to the set.
   • Update the current number to this result.
3. If the number becomes 1, return true.

Complexity:

Time Complexity: O(log₁₀(n)), where n is the input number, as there are a limited number of possible sums before repeating starts.
Space Complexity: O(log₁₀(n)), for the set storing seen sums.

Java Implementation:

public boolean isHappy(int n) {
    Set set = new HashSet(); // Track numbers to detect cycles

    while (n != 1) {
        int next = squareSum(n); // Calculate the sum of squares of digits
        if (set.contains(next)) return false; // Cycle detected
        set.add(next); // Add current sum to the set
        n = next; // Move to the next number
    }

    return true; // If n becomes 1, it's a happy number
}

public int squareSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += (n % 10) * (n % 10); // Add the square of the last digit
        n /= 10; // Remove the last digit
    }
    return sum;
}
                

Python Implementation:

def isHappy(n):
    seen = set() # Track numbers to detect cycles

    def square_sum(num):
        total = 0
        while num:
            total += (num % 10) ** 2 # Add the square of the last digit
            num //= 10 # Remove the last digit
        return total

    while n != 1:
        n = square_sum(n) # Calculate the sum of squares of digits
        if n in seen: # Cycle detected
            return False
        seen.add(n) # Add current sum to the set

    return True # If n becomes 1, it's a happy number
                

C++ Implementation:

bool isHappy(int n) {
    unordered_set seen; // Track numbers to detect cycles

    auto square_sum = [](int num) {
        int sum = 0;
        while (num) {
            int digit = num % 10;
            sum += digit * digit; // Add the square of the last digit
            num /= 10; // Remove the last digit
        }
        return sum;
    };

    while (n != 1) {
        n = square_sum(n); // Calculate the sum of squares of digits
        if (seen.count(n)) // Cycle detected
            return false;
        seen.insert(n); // Add current sum to the set
    }

    return true; // If n becomes 1, it's a happy number
}