Leetcode: Happy Number (4ms) solution

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: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1 

Hide Tags

 Hash Table Math

---------------------------------------------


The key is to find out what tells a number is not a happy number:

a good example is shown below:

1^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4

the sum '4' appears the second time, which means that the cycle will goes on and on without an end and we can judge that it's not a happy number.

A good way to judge whether one item appear more than one time is hasp table: map or unordered_map. Since we don't  need order information, we use unordered_map as speed consideration.

///////////////////////////////////////////////////
// code 4ms
class Solution {
public:
    bool isHappy(int n) {
        int j=1;
        unordered_map<int,int> tmp;
         while(1){
        int sum=0;  
           //calculate the sum
           while(n>0){
            sum+=(n%10)*(n%10);
            n=n/10;
            }
         
            tmp[sum]=j;
            //check the duplicate key in map
            if(tmp.size()<j)return false;
            else if (sum==1)return true;
            j++;
            n=sum;
        }
    }
};