[알고리즘] LeetCode 202번 "Happy Number" (C/C++) - Don 임베디드

문제요약:

Write an algorithm that determines if a number n is a "happy number"

A happy number is defined as the following process.

- Starting with any positive number, replace the number by the sum of the squares of its digits.

- Repeat the process until the number equals 1,

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.

 

제약:

1 <= n <= (2^31 -1)

 

예제 1 입력.	예제 1 출력.
19	true
예제 2 입력.	예제 2 출력.
2	false
예제 3 입력.	예제 3 출력.
1000	true

예제 1 보충설명)

19 -> 1^2 + 9^2 = 82

82 -> 8^2 + 2^2 = 68

68 -> 6^2 + 8^2 = 100

100 -> 1^2 + 0^2 + 0^2 = 1

-> return true;

 

예제 2 보충설명)

2 -> 2^2 = 4

4 -> 4^2 = 16

16 -> 1^2 + 6^2 = 37

37 -> 3^2 + 7^2 = 58

58 -> 5^2 + 8^2 = 89

89 -> 8^2 + 9^2 = 145

145 -> 1^2 + 4^2 + 5^2 = 42

42 -> 4^2 + 2^2 = 20

20 -> 2^2 + 0^2 = 4

-> return false;  // because it loops in a cycle

 

 

정답코드:

class Solution {
public:
    unordered_set<int> myHashSet;
    
    bool isHappy(int n) {
        
        long long nResult = 0;
        long long nCurrent = n;
        long long nLastDigit = 0;
        
        // get sum of squares the digits.
        while (nCurrent > 0)
        {
            nLastDigit = nCurrent % 10;
            nResult += (nLastDigit * nLastDigit);
            nCurrent /= 10;
        }
        
        // check the result
        if (nResult == 1)
        {
            return true;
        }
        else
        {
            if (myHashSet.find(nResult) != myHashSet.end())
            {
                return false;
            }
            else
            {
                // insert nResult to myHashSet.
                myHashSet.insert(nResult);
                return isHappy(nResult);
            }
        }
    }
};

 

핵심 Idea:

1. run recursive function

 

2. check if the process is in a cycle

=> used *unordered_set rather than unordered_map

because there's no need for a value. We only need a key,

which is a result of summing up squares of digits.

*참고: unordered_set vs unordered_map (https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/)

 

3. How do you know if the numbers infinitely get larger?

=> It is given that the cycle exists. It is safe to assume that the algorithm would not run infinitely.

     However, we still have to justify whether it is safe to use integers.

     In other words, we need to be sure that no nResult(sum of squares of each digits) value is larger than 2^31 -1.

     For a number of k digits, the nResult value is less than or equal to

     k * (9^2).

     Here we can see that nResult would not exceed the original number when it has 3 or more digits.

     The maximum value of an original number is given as 2^31 -1, which is within range of integer.

     Therefore, it is safe to use integer data type.

k (digits)	Max of nResult	next k (digits)
1	9^2 = 81	2
2	9^2 + 9^2 = 162	3
3	9^2 + 9^2 + 9^2 = 243	3
4	9^2 + 9^2 + 9^2 + 9^2 = 324	3
5	9^2 + 9^2 + 9^2 + 9^2 + 9^2 = 405	3

    

 

원본 링크: https://leetcode.com/problems/happy-number/