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: Create a set to track visited numbers. This helps detect cycles.
3. Sum of Squares: Calculate the sum of the squares of the digits of the current number.
4. Cycle Detection: Check if the sum of squares is already present in the set. If it is, we have a cycle, and the number is not happy.
5. Happy Number Check: If the sum of squares is 1, the number is happy.
6. Update: If the sum of squares is not 1 and not in the set, add it to the set and update n to the sum of squares. Go back to step 3.

Explanation

The algorithm uses a set to efficiently detect cycles. If we encounter a number that we've already seen, we know the process will loop endlessly without reaching 1. The set provides O(1) lookup time, making cycle detection very fast. The algorithm iteratively calculates the sum of squares until either 1 is reached (happy number) or a cycle is detected (unhappy number).

Code

#include <iostream>
#include <set>

using namespace std;

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

bool isHappy(int n) {
    set<int> seen;
    while (n != 1 && seen.find(n) == seen.end()) {
        seen.insert(n);
        n = sumOfSquares(n);
    }
    return n == 1;
}

int main() {
    int n1 = 19;
    int n2 = 2;
    cout << "Is " << n1 << " a happy number? " << (isHappy(n1) ? "true" : "false") << endl; //Output: true
    cout << "Is " << n2 << " a happy number? " << (isHappy(n2) ? "true" : "false") << endl; //Output: false
    return 0;
}

Complexity

• Time Complexity: O(log n) - In the worst case, the number of iterations is logarithmic with respect to the input number. This is because the sum of squares generally decreases as the number of digits reduces. While there's no strict upper bound, the process generally converges relatively quickly.
• Space Complexity: O(log n) - The space used by the set to store visited numbers is proportional to the number of iterations, which is again, roughly logarithmic with the input. In the worst case, the number of unique numbers encountered before a cycle is detected could be logarithmic with the input number.