###### tags: `Leetcode` `easy` `pointer` `hash` `python` `c++`

# 202. Happy Number

## [題目連結:] https://leetcode.com/problems/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.


#### [圖片來源:] https://leetcode.com/problems/happy-number/

## 解題想法:
* 題目要求:
* 拆解每位數，分別平方和重組，重複至等於1
* 若進入非1的無限循環 則為False

* **法1**: 龜兔賽跑
* 使用兩pointer
* slow為當前拆解的組合
* fast為更下次的組合

* **法2**: 用set紀錄每次遇過的數字

## Python(Sol1):

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        fast=n
        slow=n
        while fast!=1:
            fast=self.getPower(self.getPower(fast))
            slow=self.getPower(slow)
            if fast==1 or slow==1:
                return True
            if fast==slow:
                return False
        return True
    
    def getPower(self,n):
        res=0
        while n:
            res+=(n%10)**2
            n//=10
        return res

result=Solution()
ans=result.isHappy(n=19)
print(ans)

## Python(Sol2):

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        seen=set()
        while n!=1:
            n=self.getPower(n)
            if n==1:
                return True
            if n in seen:
                return False
            seen.add(n)
        return True
        
    def getPower(self,n):
        res=0
        while n:
            res+=(n%10)**2
            n//=10
        return res
        
result=Solution()
ans=result.isHappy(n=19)
print(ans)

## C++(Sol1):

#include<iostream>
#include<math.h>
using namespace std;

class Solution {
public:
    bool isHappy(int n) {
        int fast=n;
        int slow=n;
        while (fast!=1){
            fast=getPower(getPower(fast));
            slow=getPower(slow);
            if (slow==1 || fast==1)
                return true;
            if (fast==slow)
                return false;
        }
        return true;

    }
    int getPower(int n){
        int res=0;
        while (n){
            // include<math.h>
            res+=pow(n%10,2);
            n/=10;
        }
        return res;
    }
};

int main(){
    Solution res;
    int n=19;
    bool ans=res.isHappy(n);
    cout<<ans<<endl;
    return 0;
}

## C++(Sol2):

#include<iostream>
#include<set>
#include<math.h>
using namespace std;

class Solution {
public:
    bool isHappy(int n) {
        //#include<set>
        set<int> dic;
        while (n!=1){
            n=getPower(n);
            if (n==1)
                return true;
            if (dic.find(n)!=dic.end()) //find n in set
                return false;
            dic.insert(n);
        }
        return true;
    }
    int getPower(int n){
        int res=0;
        while (n){
            // include<math.h>
            res+=pow(n%10,2);
            n/=10;
        }
        return res;
    }
};

int main(){
    Solution res;
    int n=19;
    bool ans=res.isHappy(n);
    cout<<ans<<endl;
    return 0;
}