202. Happy Number

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.

解法

1. 這種一個整數要把數字位數分解出來的題目，可以使用mod以及divide來分解出來 所以會有一個方法去加總每個數字位數的平方：

    public int getNext(int n){
        int res =0;
        while(n != 0){
            int d = n % 10;
            n /= 10;
            res += (int)Math.pow(d,2);
        }
        return res;
    }

而HappyNumber有幾種情況：

1. getNext()答案是1，就直接跳出答true
2. getNext()卡進一個無限迴圈，數字不斷重複出現（如下圖），因此有兩種解法

法一：HashSet

Set的特徵：一個元素只能在其中存在一次，而set的add方法會回傳是否新增成功，因此：

    public boolean isHappy(int n) {
        Set<Integer> setInt = new HashSet<>();
        int init = getNext(n);
        boolean res =  true;
        while(init != 1){
            if(!setInt.add(init)){
                res= false;
                break;
            }
            init = getNext(init);
        }
        return res;
    }

如果一個元素存在第二次了，就跳出回傳false

The reason we use a HashSet 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)O(1)O(1) time, whereas for the other data structures it takes O(n)O(n)O(n)time. Choosing the correct data structures is an essential part of solving these problems.

Time complexity : O(logn)

法二：龜兔賽跑Pointer

如上方所示，可能會進一個迴圈，因此可以用龜兔賽跑的方法來看是否卡進一個迴圈，兔子走兩步、烏龜走一步，若兩者重疊就代表重複了。

class Solution {
    public int getNext(int n){
        int res =0;
        while(n != 0){
            int d = n % 10;
            n /= 10;
            res += (int)Math.pow(d,2);
        }
        return res;
    }
    public boolean isHappy(int n) {
        int turtle = getNext(n);
        int rabbit = getNext(getNext(n));
        boolean res = true;
        while(turtle != 1){
            if(turtle == rabbit){
                res = false;
                break;
            }
            turtle = getNext(turtle);
            rabbit = getNext(getNext(rabbit));
        }
        return res;
    }
}

Time complexity : O(logn)