# 202 - Happy Number

解法一 - Hash Table

基本上就是紀錄數字有沒有出現過，實作如下：

class Solution {
public:
    bool isHappy(int n) {
        if(n == 1) return true;
        int x = n;

        unordered_set<int> table;
        table.insert(n);

        while(x != 1) {
            int tmp = 0;

            int digit;
            while(x) {
                digit = x % 10;
                tmp += pow(digit, 2);
                x /= 10;
            }

            if(tmp == 1)
                return true;
            if(table.find(tmp) != table.end())
                break;

            table.insert(tmp);
            x = tmp;
        }

        return false;
    }
};

解法二 - Fast & Slow Pointer

我們可以把 Happy Number 視為一個最後會卡在 1 這個 loop 的 cycled linked list，而其他會卡在不是 1 的 loop 的數字，就是非 Happy number，所以可以實作如下：

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        while(true) {
            slow = nextNum(slow), fast = nextNum( nextNum(fast) );

            if(slow == fast && slow == 1) { break; }
            else if(slow == fast && slow != 1) { return false; }
        }

        return true;
    }

private:
    int nextNum(int num) {
        int next = 0;

        while(num > 0) {
            int digit = num % 10;
            next += pow(digit, 2);
            num /= 10;
        }

        return next;
    }
};

寫 while(true) 這種 code 實在不怎麼好，我們可以用 do ... while 改寫：

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = nextNum(slow);
            fast = nextNum( nextNum(fast) );
        }while(slow != fast);

        return slow == 1;
    }

private:
    int nextNum(int num) {
        int next = 0;

        while(num > 0) {
            int digit = num % 10;
            next += pow(digit, 2);
            num /= 10;
        }

        return next;
    }
};