# 202 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:

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

如題目範，19拆成 1平方+ 9平方…持續進行計算，到1即為happy數字。當中要判斷是否有可能是循環即永遠無法成為1。

個人想到的作法，用Math.pow方法來找個位數、十位數，實事證明這是很爛的方法，但解題思維是一樣的，只是採用很爛的計算方法。將N值拆成個位平方 + 十位平方 + 百位平方…且用max值來與N值相比，比N大就跳出while迴圈。也有考慮到可能會遇到無限迴圈的問題，用集合物件去處理…。但只勝過10%的解法…時間複雜度與空間複雜度是都是最差的。

Runtime: 3 msMemory Usage: 33.7 MB

程式碼:

class Solution {
    int h = 0; //當達到條件不再執行時的最後HAPPY值
   Set<Integer> set = new HashSet<>(); //判斷是否進入無限循環
    public boolean isHappy(int n) {
        if(n == 1){
            return true;
        }
          process(n);
        // System.out.println("return h = "+ h );    
        return h == 1? true: false;
    }
    public void process(int a){
        int happy = 0 ; //total happy , ex: 49 , happy ==> 16 + 81 = 97 
        int c = 0; // ex :c =1 10 , c = 2 100 , c =3 1000....
        int check  = 1; //single happy  ex: 49 ,once while check == 4*4 ==> 16 ,twince check == 9*9 ==> 81
        long max = 0;  //if max > a break while loop
        while(max <= a){
            check = (int)(a / Math.pow(10, c) % 10);
            happy += Math.pow(check,2);
            // System.out.println(a+ " , chcek = " + check + " , c = " + c + " , happy = " + happy + " , max = "+ max);
            c++;
            max = (long) Math.pow(10, c);
        } 
        
        // System.out.println("set.contains(happy)= " + set.contains(happy));
        if(happy > 2 && !set.contains(happy)){
             set.add(happy);
            process(happy);
        }else{
            // System.out.println("return happy = "+ happy);
            h = happy;
        }
        
        // System.out.println(a+ " , chcek = " + check + " , c = " + c + " , happy = " + happy + " , max = "+ max );
    }
}

一樣用遞廻的方式來處理 。但計算個位數、十位數、百位數用簡單且有效的方法。

以n = 106為例。第一次進入while loop的情況。

1 while run 1 n = 106 , di = 106%10 ==> 6 , sum = 0, sum += 6*6 = 0+36 ==> 36 ,n = n/10 = 106 /10 ==> 10

2 while run 2 n = 10 , di = 10%10 ==> 0 , sum = 36, sum += 0*0 = 36+0 ==> 36 ,n = n/10 = 10 /10 ==> 1

3 while run 3 n = 1 , di = 1%10 ==> 1 , sum = 36, sum += 1*1 = 36+ 1 ==> 37 ,n = n/10 = 1 /10 ==> 0

n == 0 跳出While 再由sum再代入遞迴……

勝過60%的解法

Runtime: 2 msMemory Usage: 33.7 MB

程式碼:

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>(); //判斷是否進入無限循環
        return happ(set,n);
	}

    public boolean happ(Set<Integer> se88 , int s){
        se88.add(s);
        int sum = 0;
        while(s!= 0){
            sum+= (s%10) * (s%10);
            s = s/10;
        }
        if(sum == 1){
            return true;
        }
        if(se88.contains(sum)){
            return false;
        }
        return happ(se88, sum);
    }
}

把遞廻用while(true)來代替遞廻，將n = sum，只有當符合if條件才會回傳。計算方式不變。加快其執行速度。

勝過94%的解法

Runtime: 1 msMemory Usage: 33.4 MB

class Solution {
    public boolean isHappy(int n) {
        List<Integer> arr = new ArrayList<>();
        while (true) {
            int sum = 0;
            while (n > 0) {
                int dig = n%10;
                sum += dig*dig;
                n /= 10;
            }
            if (sum == 1)
                return true;
            if (arr.contains(sum))
                return false;
            else
                arr.add(sum);
            n = sum;
        }
    }
} 

最快的是再次呼叫isHappy方法，但重點是少用一個集合物件，因為進入無限循環，一定會進入個位數的平方，1-9這裡除了1之外，還有7最後也轉到1，所以除1、7之外，其它小於10的2,3,4.....都會是無限廻圈，因此不需要用集合物件來記錄每次while後的sum值，以用來判斷集合物件是否已存有相同的n值？有，表示進入無限循環就要回傳false。沒有，表示還沒進入無限循環。再者也只用一個while迴圈少了while(true)。沒有符合if條件，回傳直接就再呼叫自已本身。

勝過100%的解法

Runtime: 0 msMemory Usage: 32.8 MB

程式碼:

class Solution {
    public boolean isHappy(int n) {
        if(n<10) {
		if(n==1||n==7) return true;
	    return false;
	 }
	int b;int sum=0;
	while(n>0) {
		  b=n%10;
		  sum=sum+b*b; 
		  n=n/10;
	  } 
     return isHappy(sum);
    }
}