202. Happy Number

problem description

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

algorithm thought

这题其实就是链表判圈问题的建模版本，happy number问题会有两种情况，一种就是能找到结果，结果为1，还有一种就是会一直循环，形成一个圈。

把结果能得到1的，认定为是没有圈的链表，而会一直循环的happy number认定为是带圈的链表，最后就是找出圈就行。

链表找环问题可以看前面的题解。

code

class Solution {
public:
    bool isHappy(int n) {
        int fast=n;
        int slow=n;
        while(1){
            fast=happy(happy(fast));
            slow=happy(slow);
            if(fast==1)
                return true;
            if(fast==slow)
                return false;
        }
        return false;
    }
    int happy(int a){
        int res=0;
        while(a){
            res+=(a%10)*(a%10);
            a=a/10;
        }
        return res;
    }
};

algorithm analysis

时间复杂度O(n)，重要的是，空间复杂度只有O(1)。如果用一个hashtable保存之前出现的数字，也是能找到重复的，但是这样就需要O(n)的时间复杂度了。