### Leetcode: 202. Happy Number

Determining Happy Numbers in C++

# 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;
}
}

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!