Wednesday, April 29, 2015

LeetCode [202] Happy Number

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, 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.

Return True if n is a happy number, and False if not.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Accepted
526,479
Submissions
1,044,315
//C++: 10ms
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> cycle;
        while(n>1 && cycle.find(n)==cycle.end()){
            cycle.insert(n);
            int sum = 0;
            while(n){
                int t = n%10;
                sum += t*t;
                n = (n-t)/10;
            }
            n = sum;
        }
        return n==1;
    }
};

//Java
class Solution {
    int getNext (int n)
    {
        int ret = 0;
        while(n>0)
        {
            int d = n%10;
            ret += d*d;
            n = n/10;
        }
        return ret;
    }

    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n!=1 && !set.contains(n))
        {
            set.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

No comments:

Post a Comment