---
# System prepended metadata

title: \#202 Happy Number
tags: [leetcode, leetcode-easy]

---

# \#202 Happy Number
## *給定一正整數,當此數的每一位數平方和為1時,表示其為"Happy Number", return true(當<>1時,就持續用相同方式計算直到符合條件); 否則return false*
## Log 
 - build 20210424 by syhuang

## 快慢指針法(佛洛伊德演算法)
 - 題目的計算方式, 其最後必會收斂為一數字group, 套用最短路徑算法(佛洛伊德演算法), 然後加上條件:節點數為1的時候就是Happy Number; 節點重複時且<>1表示進入loop, 不是Happy Number
 - 此算法效率較佳
```javascript=
var isHappy = function(n) {
    var slow = getSquareSum(n);
    var fast = getSquareSum(slow);
    while(fast!=1 && fast!=slow){
        slow = getSquareSum(slow);
        fast = getSquareSum(getSquareSum(fast));
    }
    return fast == 1;
    function getSquareSum(num){
        var result = 0;
        num.toString().split('').forEach(function(val){
            result+=val*val;
        });
        return result;
    }
};
```
## 初見
 - 用map紀錄每次計算的結果, 判斷是否出現過同樣的數字(表示loop, 此數不為Happy Number)
```javascript=
var isHappy = function(n) {
    var map = new Map();
    var isHappy=false,t=n;
    while(!map.has(t) && !isHappy){
        var ary = t.toString().split('');
        var sum = 0;
        ary.forEach(function(val){
            sum+=val*val;
        });
        if(sum===1) isHappy=true;
        map.set(t,sum);
        t = sum;
    }
    return isHappy;
};
```
## 備註
 - 此題解題的隱藏前題:任意正整數的每位數平方和, 其以相同方式持續不斷計算, 最後必定收斂到某一個數字group中循環; 而當這個group只有一個數字"1"時(1^2=1, 因此變成1循環), 就是此題要求的Happy Number(註1)
## 參考
 - [註1](https://leetcode.com/problems/happy-number/discuss/56919/Explanation-of-why-those-posted-algorithms-are-mathematically-valid)
###### tags: `leetcode`, `leetcode-easy`