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: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

解題思路

1. 先檢查一個數字，字元的平方和，然後放到容器裡。

2. 檢查是否有重複出現的平方和，避免無限迴圈。

程式解答

class Solution 
{
public:
    bool isHappy(int n) 
    {
        int i = 0;
        int ans = 0;

        vector<int> p;
        vector<int>::iterator it;
        
        while (n)
        {
            i = n % 10;
            ans = ans + i * i;
            n /= 10;
            
            if (!n)
            { 
                if (ans == 1)
                    return true;
                
                it = find(p.begin(), p.end(), ans);
                if (it != p.end())
                    return false;
                
                p.push_back(ans);
                n = ans;
                ans = 0;
            }
        }
        
        return false;
    }
};