Q7. A 'OverHappy' number follows the following criteria :

It is always a positive integer. The integer number is replaced by the sum of the squares of its digits and this process is repeated until the sum equals 1.
 The numbers for which the loop runs endlessly and never reach to the sum of 1 are not OverHappy numbers.

Write a program that print true if n is OverHappy number else print false.

Intuition Behind the Algorithm

The algorithm is designed to determine whether a given positive integer is an "OverHappy Number." This concept is rooted in a repetitive process where a number is transformed by replacing it with the sum of the squares of its digits. If this iterative process eventually leads to the number 1, the number is deemed "OverHappy." The challenge lies in identifying numbers for which this process endlessly continues without reaching 1, classifying them as not "OverHappy."

#include <bits/stdc++.h>
using namespace std;

// Function to update the number to the sum of the squares of its digits
int update(int n) {
    int s = 0;
    while (n > 0) {
        int ld = n % 10; // Extract the last digit
        s += ld * ld;    // Add the square of the last digit to the sum
        n /= 10;         // Remove the last digit
    }
    return s;
}

// Recursive function to check if a number is an OverHappy number
bool check(unordered_map<int, bool> &m, int n) {
    if (n == 1)
        return true; // Base case: if the number becomes 1, it's OverHappy

    if (m.find(n) != m.end())
        return false; // If the number is already in the map, it's not OverHappy

    m.insert(make_pair(n, true)); // Insert the number into the map
    n = update(n);                // Update the number to the sum of the squares of its digits
    return check(m, n);           // Recursively check the updated number
}

// Wrapper function to initiate the check for OverHappy number
bool isHappy(int n) {
    unordered_map<int, bool> m; // Map to keep track of numbers encountered

    return check(m, n); // Start the recursive checking process
}

// Main function to take input and output results
int main() {
    int n;
    cin >> n; // Input the number

    bool ans = isHappy(n); // Check if the number is OverHappy

    // Output the result
    if (ans)
        cout << "Over Happy Number" << endl;
    else
        cout << "Not an Over Happy Number" << endl;

    return 0;
}

Code Walkthrough

The C++ code provided employs several functions to solve this problem:

• update(int n): This function takes an integer and returns the sum of the squares of its digits. It repeatedly divides the number by 10 (extracting digits) and accumulates the squares of these digits.

• check(unordered_map<int, bool> &m, int n): A recursive function that uses a hash map to track the numbers encountered during the process. If the number becomes 1, it returns true, indicating the number is "OverHappy." If a number repeats (found in the map), it indicates a cycle, returning false.

• isHappy(int n): This is the main function that initializes the hash map and starts the recursive checking process.

• main(): The entry point of the program, where the user inputs a number, and the program outputs whether it is "OverHappy" or not.

Time and Space Complexity Analysis

• Time Complexity: The time complexity is not straightforward due to the nature of the problem. However, it can be argued that for most practical inputs, the function will resolve in polynomial time since the sum of the squares of the digits decreases rapidly for large numbers.

• Space Complexity: The space complexity primarily depends on the hash map used to store intermediate numbers. In the worst case, this can grow to a size proportional to the number of unique sums generated by the number's digits, which is O(log n) in most cases.

Key Points of the Algorithm

• Avoiding Infinite Loops: The use of a hash map to track previously seen numbers is crucial in preventing infinite loops for numbers that are not "OverHappy."

• Recursive Approach: The recursive implementation simplifies the process of continually updating a number until a conclusion is reached.

• Efficiency: The algorithm is efficient for numbers that quickly converge to 1. Its performance may vary for larger numbers or those leading to long cycles.