Leetcode: Happy Number

Write an algorithm to determine if a number 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, and 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 numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Understand the problem:
The hint of the problem is if the input number is a happy number, it will end with 1. 
Else, it will loop endlessly in a cycle. Therefore, we could use a hash set to keep track of each number we have visited. If we saw a visited number, that means the loop has been formed and it will return a false. 

Code (Java):

public class Solution {
    public boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        
        while (true) {
            int square = getSumOfSquare(n);
            
            if (square == 1) {
                return true;
            } else if (set.contains(square)) {
                return false;
            }
            
            set.add(square);
            n = square;
        }
    }
    
    private int getSumOfSquare(int n) {
        int result = 0;
        
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            result += digit * digit;
        }
        
        return result;
    }
}

An O(1) space solution:

int digitSquareSum(int n) {
    int sum = 0, tmp;
    while (n) {
        tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow, fast;
    slow = fast = n;
    do {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(fast);
        fast = digitSquareSum(fast);
    } while(slow != fast);
    if (slow == 1) return 1;
    else return 0;
}

Questions: Why unhappy number must end with a loop?
There is a proof from wiki:
https://en.wikipedia.org/wiki/Happy_number

Numbers that are happy, follow a sequence that ends in 1. All non-happy numbers follow sequences that reach the cycle:

4, 16, 37, 58, 89, 145, 42, 20, 4, ...

To see this fact, first note that if n has m digits, then the sum of the squares of its digits is at most ${\displaystyle 9^{2}m}$, or ${\displaystyle 81m}$.

For ${\displaystyle m=4}$ and above,

${\displaystyle n\geq 10^{m-1}>81m}$

so any number over 1000 gets smaller under this process and in particular becomes a number with strictly fewer digits. Once we are under 1000, the number for which the sum of squares of digits is largest is 999, and the result is 3 times 81, that is, 243.

• In the range 100 to 243, the number 199 produces the largest next value, of 163.
• In the range 100 to 163, the number 159 produces the largest next value, of 107.
• In the range 100 to 107, the number 107 produces the largest next value, of 50.

Considering more precisely the intervals [244,999], [164,243], [108,163] and [100,107], we see that every number above 99 gets strictly smaller under this process. Thus, no matter what number we start with, we eventually drop below 100. An exhaustive search then shows that every number in the interval [1,99] either is happy or goes to the above cycle.

The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.