Leetcode: 202. Happy Number

Determining Happy Numbers in C++

Introduction: In this blog post, we'll explore a C++ solution to determine whether a given number is happy or not. A happy number is a positive integer that, when repeatedly replaced by the sum of the squares of its digits, eventually reaches 1. Understanding how to efficiently check for happy numbers can be useful in various scenarios, such as in number theory or programming challenges involving mathematical properties.

Problem Description: The problem can be defined as follows: Given a positive integer n, we need to determine if it is a happy number. A happy number is one where the sum of the squares of its digits, when calculated repeatedly, eventually leads to 1. If the process results in a cycle that doesn't reach 1, the number is not happy.

Approach: To solve this problem, we will implement two functions: getNext and isHappy. The getNext function calculates the sum of the squares of the digits of a given number, and the isHappy function uses the getNext function to determine if the number is happy.

#include <unordered_set>

class Solution {
private:
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

public:
    bool isHappy(int n) {
        std::unordered_set seen;
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }
};

Explanation: Let's break down the implementation step by step: 1. We define a helper function called getNext that calculates the sum of the squares of the digits of a given number n. 2. The while loop inside getNext runs until n becomes 0, extracting each digit and adding its square to the totalSum. 3. The totalSum represents the sum of the squares of the digits of the original number. 4. The function returns totalSum, which will be used in the isHappy function. 5. In the isHappy function, we use an unordered_set to keep track of the numbers we've seen so far during the calculation process. 6. The while loop in isHappy runs until the number becomes 1 (a happy number) or we detect a cycle (a non-happy number). 7. Within the loop, we insert the current number into the seen set and update the number to the next one using the getNext function. 8. If the loop terminates with n == 1, the function returns true, indicating that the number is happy. 9. If the loop terminates with a number that has been seen before (cycle detected), the function returns false, indicating that the number is not happy.

Example: Let's illustrate the implementation with an example. Consider the input number n = 19:

1. Initially, we start with n = 19.
2. getNext(19) calculates the sum of the squares of its digits: 1^2 + 9^2 = 82.
3. Now, we update n to 82.
4. getNext(82) calculates the sum of the squares of its digits: 8^2 + 2^2 = 68.
5. Now, we update n to 68.
6. getNext(68) calculates the sum of the squares of its digits: 6^2 + 8^2 = 100.
7. Now, we update n to 100.
8. getNext(100) calculates the sum of the squares of its digits: 1^2 + 0^2 + 0^2 = 1.
9. The loop terminates as n becomes 1, and the function returns true, indicating that the number 19 is a happy number.

Conclusion: We have successfully implemented a C++ solution to determine whether a given number is a happy number or not. The provided functions, getNext and isHappy, efficiently calculate the sum of squares of digits and detect cycles using an unordered_set, making it an optimal solution. Understanding this bit manipulation technique can be useful in various programming tasks that involve mathematical properties and cyclic patterns. Whether you're working on number theory or solving programming challenges, this knowledge can prove invaluable. Happy coding!