# Leetcode 解題速記 202. Happy Number
###### tags: `LeetCode` `C++`
題敘:
---
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 <= n <= 231 - 1

解題筆記:
---
最直觀的做法是開一個陣列儲存每一次計算的值，並用函數遍歷該陣列比對值是否重複
若重複且=1則回傳true
但不確定Judge測資運算後上界的情況下使用陣列情況過於複雜，因此考慮其他寫法。

這題是典型的Cycle Finding題，這邊使用佛洛伊德的龜兔賽跑演算法
開兩個變數，一個走快一個走慢，當兩個變數遍歷陣列時相遇代表此陣列必定為Cycle


VisuAlgo圖像化 : [https://visualgo.net/en/cyclefinding](https://)

測資範例:

Input: n = 19
Output: true
Explanation:
1^1 + 9^9 = 82
8^8 + 2^2 = 68
6^6 + 8^8 = 100
1^1 + 0^0 + 0^0 = 1

故程式碼只要執行到兩個變數皆為1即可 (return true)

程式碼:
---

int cycle(int);

bool isHappy(int n){
    int slow=n;
    int fast=n;
    do{
        slow=cycle(slow);
        fast=cycle(fast);
        fast=cycle(fast);
    }while(slow!=fast);
    return fast==1;
}

int cycle(int n){
    int r=0;
    while(n!=0){
        int d=n%10;
        n/=10;
        r+=d*d;
    }
    return r;
}