# Mathematical explanation and proof. plus two common solutions

• I started solving it just according to the definition, and then started wonder why the number must be a either a loop or 1. i think it's a good practice to demonstrate problem solving process. Here is my brief observation to simplify the explanation, hope it would help

1. Suppose number n has m digit.

2. Each digit can be maximally 9, so the next number max n' = 81m < n (for any m>=4)
(e.g. 9999, has 4 digits, next number would be 81*4=324)
-->so conclude that any number we start, it'll drop under 1000,

3. For number 1-1000, we can prove by brutal force that it'll either end with 1 or a loop.
-->for any positive integer, it will either be 1 or loop.

Below is the program to prove this

``````public void proveTheory() throws Exception {
for (int i = 1; i < 1000; i++) {
//since it's to prove the theory, we cannot assume a number would either end in 1 or cycle
//put a limit on the for loop

HashSet<Integer> set = new HashSet<>();
int num = i;
for (int j = 0; j < 10000; j++) {
if (set.contains(num) || num == 1) break;
num = next(num);
}

if (!set.contains(num) && num != 1) throw new Exception(num + " is neither happy nor loop");
}
}

private int next(int num) {
int next = 0;
while (num != 0) {
next += (num % 10) * (num % 10);
num /= 10;
}
return next;
}
``````

What's provided above is only simple ways to prove it. Wiki has the full definition with more math to narrow down the range of search https://en.wikipedia.org/wiki/Happy_number

With the above analysis, the question basically becomes cycle detection in linked list, below is two solutions

Floyd Loop Detection as used in linked list

``````public boolean isHappy(int n) {
int n1 = n, n2 = n;

while (n1 != 1) {
n1 = next(n1);
n2 = next(next(n2));
if (n1 == n2) break;
}

return n1 == 1;

}
``````

Use HashSet to record visited number

``````public boolean isHappy(int n) {

HashSet<Integer> visited = new HashSet<>();
int num = n;
while (num != 1 && !visited.contains(num)) {