Understanding Happy Number (LeetCode 202) – HashSet + Cycle Detection

#dsa #beginners #cpp #programming

Today I solved a classic problem that looks simple but teaches an important concept: cycle detection using a HashSet.

Problem Summary

A number is called a Happy Number.If replace the number with the sum of squares of its digits.Repeat the process if it eventually becomes 1, it is happy.If it enters a loop and never reaches 1, it is not happy.

Example

Input:-> n = 19

Process:

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

Since it reaches 1, the answer is true.

Key Idea

1) The tricky part is:

-> Some numbers fall into an infinite cycle.

2) So how do we detect that?

3) We store already seen numbers inside a HashSet.

4) If a number repeats → we are in a cycle → return false.

C++ Implementation

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

public:
    bool isHappy(int n) {
        unordered_set<int> ust;

        while(n != 1 && ust.find(n) == ust.end()){
            ust.insert(n);
            n = SqrtOfSum(n);
        }

        return n == 1;
    }
};