Happy Number

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. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. If the number is a happy number, return true; otherwise, return false.

Sample Input:

19

Expected Output:

true

In this example, the process goes as follows:

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

As the process eventually leads to 1, the number 19 is a happy number, and the expected output is true.

Time and Space Complexity:

The time complexity of the algorithm is a bit tricky to determine. In the worst case, the algorithm could run indefinitely for numbers that are not happy, but it has been proven that non-happy numbers always end up in a cycle containing 4. Therefore, we can say that the algorithm will run in constant time for all practical purposes. The space complexity is O(1) as we are using only a constant amount of additional memory.

Now, let’s provide the C++ solution with comments explaining the code:

#include <iostream>
#include <unordered_set>

// Helper function to compute the sum of squares of digits in a number
int getSumOfSquares(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    std::unordered_set<int> seen; // To keep track of numbers seen during the process

    while (n != 1 && seen.find(n) == seen.end()) {
        seen.insert(n);
        n = getSumOfSquares(n);
    }

    return n == 1;
}

int main() {
    int num = 19;
    if (isHappy(num)) {
        std::cout << num << " is a happy number.\n";
    } else {
        std::cout << num << " is not a happy number.\n";
    }

    return 0;
}

The isHappy function uses a set to keep track of the numbers encountered during the process. It repeatedly computes the sum of squares of digits until either the number becomes 1 (a happy number) or a previously encountered number is found, indicating a cycle. In the latter case, the function returns false.

In the given example, the function will correctly determine that the number 19 is a happy number, and the output will be true.

As mentioned earlier, the time complexity is considered constant for practical purposes since it is bounded by the cycle involving the number 4, and the space complexity is O(1) as we are using only a constant amount of additional memory.