# PROBLEM LINK:

* Author:* Sumukh Bhardwaj

*Rahul Sharma*

**Tester:***Sumukh Bhardwaj*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Basic Programming

# PROBLEM:

Given a number N keep finding the sum of squares of all the digits of N unless it becomes equals to 1 or the sum repeats.

Return `1`

if the number ends at value 1, otherwise, return 0.

# QUICK EXPLANATION:

Simulate the process and keep a note of all the sum achieved so far if the sum is repeated return 0 otherwise 1.

# EXPLANATION:

There are 2 parts to the algorithm weâ€™ll need to design and code.

- Given a number n, what is its
*next*number? - Follow a chain of numbers and detect if weâ€™ve entered a cycle.

*Part 1* can be done by using the division and modulus operators to repeatedly take digits off the number until none remain, and then squaring each removed digit and adding them together. Have a careful look at the code for this, â€śpicking digits off one-by-oneâ€ť is a useful technique youâ€™ll use for solving a lot of different problems.

*Part 2* can be done using a **HashSet/unordered map**. Each time we generate the next number in the chain, we check if itâ€™s already in our HashSet.

- If it is
*not*in the HashSet, we should add it. - If it
*is*in the HashSet, that means weâ€™re in a cycle and so should return`false`

.

The reason we use a **HashSet/unoredred_map** and *not* a Vector, List, or Array is because weâ€™re repeatedly checking whether or not numbers are in it. Checking if a number is in a HashSet takes O(1) time, whereas for the other data structures it takes O(n) time. Choosing the correct data structures is an essential part of solving these problems.

# COMPLEXITIES

Here N is the number given.

**TIme Complexity:** O(log N).

**Space Complexity:** O(log N).

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
long long find(long long n)
{
long long ans=0;
while(n)
{
ans+=(n%10)*(n%10);
n=n/10;
}
return and;
}
long long isHappy(long long n) {
unordered_map<int, int> mark;
while(n != 1 && mark[n] == 0)
{
mark[n] = 1;
n = find(n);
}
return n == 1;
}
int main() {
ios_base::sync_with_stdio(false);
long long t,k;
cin>>t;
while(t--)
{
cin>>k;
cout<<isHappy(k)<<endl;
}
return 0;
}
```