202 - Happy Number

#easy

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.

Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路

這道題目看上去貌似一道數學問題，其實並不是！

題目中說了會 無限循環，那麼也就是說求和的過程中，sum會重複出現，這對解題很重要！

當我們遇到了要快速判斷一個元素是否出現集合裡的時候，就要考慮哈希法了。

所以這道題目使用哈希法，來判斷這個sum是否重複出現，如果重複了就是return false， 否則一直找到sum為1為止。

Solution

class Solution {
public:
    int getSum( int n ) {
        int sum = 0;
        while ( n ) {
            sum += ( n % 10 ) * ( n % 10 );
            n = n / 10;
        }

        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> set;
        while ( 1 ) {
            int sum = getSum(n);
            if ( sum == 1 ) return true;
            // 如果這個sum曾經出現過，說明已經陷入了無限循環了，立刻return false
            if ( set.find(sum) != set.end() ) {
                return false;
            }
            else {
                set.insert(sum);
            }

            n = sum;
        }
    }