**Easy**

Write an algorithm to determine if a number `n`

is happy.

A **happy number** is a number defined by the following process:

- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it
**loops endlessly in a cycle**which does not include 1. - Those numbers for which this process
**ends in 1**are happy.

Return `true`

*if* `n`

*is a happy number, and* `false`

*if not*.

**Example 1:**

Input:n = 19Output:trueExplanation:1^{2}+ 9^{2}= 82 8^{2}+ 2^{2}= 68 6^{2}+ 8^{2}= 100 1^{2}+ 0^{2}+ 0^{2}= 1

**Example 2:**

Input:n = 2Output:false

**Constraints:**

`1 <= n <= 2`

^{31}- 1

#### Algorithm

`isHappy()`

determines whether a given number is happy or not.- If the number is greater than 0, then calculate
`remainder`

by dividing the number with 10. - Calculate square of
`remainder`

and add it to a variable`result`

. - Divide number by 10.
- Repeat these steps from
`1,2 and 3`

till the sum of the square of all digits present in number has been calculated. - Finally, return the
`result`

.

- If the number is greater than 0, then calculate
- Define and initialize variable
`cur_number`

. - Calculate
`getSumOfSquareOfDigits`

- If the result is 1 then the number is a happy number.
- Store the ouput of
`getSumOfSquareOfDigits`

in a`HashSet`

to check if we are in a loop, if so, the return`false`

.

```
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
int cur_number = n;
while(true){
cur_number = getSumOfSquareOfDigits(cur_number);
if(cur_number == 1){
return true;
}
if(seen.contains(cur_number)){
return false;
}
seen.add(cur_number);
}
}
private int getSumOfSquareOfDigits(int n){
int result = 0;
while(n > 0){
int remainder = n %10;
result = result + (remainder * remainder);
n = n /10;
}
return result;
}
}
```

#### Approach 2: Floyd’s Cycle-Finding Algorithm

**Intuition**

The chain we get by repeatedly calling `getSumOfSquareOfDigits(n)`

is an *implicit* **LinkedList**. *Implicit* means we don’t have actual LinkedNode’s and pointers, but the data does still form a LinkedList structure. The starting number is the head “node” of the list, and all the other numbers in the chain are nodes. The next pointer is obtained with our `getSumOfSquareOfDigits(n)`

function above.

Recognizing that we actually have a LinkedList, it turns out that this question is almost the same as detecting if a linked list has a cycle. Therefore we can use Floyd’s Cycle-Finding Algorithm here. This algorithm is based on 2 runners running around a circular race track, a fast runner and a slow runner. In reference to a famous fable, many people call the slow runner the “tortoise” and the fast runner the “hare”.

Regardless of where the tortoise and hare start in the cycle, they are guaranteed to eventually meet. This is because the hare moves one node closer to the tortoise (in their direction of movement) each step.

```
class Solution {
public int getSumOfSquareOfDigits(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getSumOfSquareOfDigits(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getSumOfSquareOfDigits(slowRunner);
fastRunner = getSumOfSquareOfDigits(getSumOfSquareOfDigits(fastRunner));
}
return fastRunner == 1;
}
}
```

**Time Complexity :**`O(logn)`

**Space Complexity :**`O(1)`

Categories: Linked List