今天不快樂，所以寫個快樂數字。

題目

• 給定一個數字，寫一個演算法判斷是不是快樂數字，回傳true or false
• 快樂數字
  • 數字中每個位數的平方後的總和取代原本的數字
  • 重複至數字為1，即判定為快樂數字
• Example: 19
  • 
  • 
  • 
  • 
    return true

解析

• 可以看到重複在做每位數平方後總和，我們能先將這重複的動作寫成一個function。
  這裡基本的數學:
  n mod 10 能得到個位數
  n / 10 能把個位數去掉

  int squareNumber(int n){
      while(n){
      int sum = 0;
          int digit = n % 10; 
          sum += digit * digit;
          n = n / 10;
      }
      return sum;
  }
  

• 再來應該很容易觀察到，今天重複上面的function，數字可能會進入無限循環，當循環中沒有1，那就卡死啦。所以當有週期性，即要返回false，因為永遠不會是快樂數字。

循環檢測 (cycle detection)

• 是一個演算法問題
• 用於找出以疊代函數產生的序列的週期。
  • ,where
  • 以圖來說，如果有週期性，不管從黃色點點或是藍色點點開始走。都會進入循環。
    

1. Floyd Cycle Detection Algorithm

• 又稱龜兔賽跑算法(Tortoise and Hare Algorithm)
• 龜兔從起點同時出發，龜走一步、兔就走兩步。由於兔比龜快，當龜兔都在循環之中，兔會領先數圈、從後方追上龜，所以當龜兔相遇時，必定是循環中已經過一輪，我們就能跳出迴圈。
• 因為只要2個變數就能找到循環，所以非常省記憶體!
  

Code

class Solution {
public:
    int squareNumber(int n){
        int sum = 0;
        while(n){
            int digit = n % 10;
            sum += digit * digit;
            n = n / 10;
        }
        return sum;
    }
    
    bool isHappy(int n) {
        int rabbit = n;
        int turtle  = n;
        
        do{
            turtle = squareNumber(turtle);  //run 1 step
            rabbit = squareNumber(squareNumber(rabbit)); // run 2 steps
        }while(turtle != rabbit); //check
        
        return (turtle == 1);
    }
};