[LeetCode Road] Happy Number - Solution/C++

202. Happy Number

Question:

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:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Source code

Version 1

Idea:
At first, I suggest you realizing what is unhappy number? You will find out the rule. E.g., n = 48
4² + 8² = 80
8² + 0² = 64
6² + 4² = 52
5² + 2² = 29
2² + 9² = 85
8² + 5² = 89
8² + 9² = 145
1² + 4² + 5² = 42
4² + 2² = 20
2² + 0² = 4
4² = 16
1² + 6² = 37
3² + 7² = 58
5² + 8² = 89

From the above example, you can find the regular process. If a number is unhappy number, the output will repeat. (In this case, 89 is repeated number)

Hence, you can take the unordered_map container to store each output.
Then, use count() to check whether the output exists in container or not, if it has already existed, count() will return false, and it means a number is unhappy number. On the contrary, if the ouput is 1, break the while() and return true.

Time complexity: O(log(n))
Space complexity: O(n)

class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int, int> umap;
        while(n != 1){
            int sum = 0;
            while(n != 0){
                sum += pow(n%10, 2);
                n /= 10;
            }
            if(umap.count(sum)) return false;
            umap.insert(pair<int,int>(sum, sum));
            n = sum;
        }
        return true;
    }
};

Version 2

Idea:
We can also adopt Floyd's Cycle Finding Algorithm, the program will stop at the same number. Then, if this number is 1, return true. Otherwise, return false.

Time complexity: O(log(n))
Space complexity: O(1)

class Solution {
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = n;
        do{
            slow = nextvalue(slow);
            fast = nextvalue(fast);
            fast = nextvalue(fast);
        }while(slow != fast);
        if(slow == 1) return true;
        return false;
    }
private:
    int nextvalue(int n){
        int sum = 0;
        while(n){
            sum += pow(n%10, 2);
            n /= 10;
        }
        return sum;
    }
};