[C++] LeetCode : 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.

 

숫자 n이 행복한지 확인하는 알고리즘을 작성하십시오.

행복한 숫자는 다음 프로세스에 의해 정의된 숫자입니다.

임의의 양의 정수로 시작하여 숫자를 해당 자릿수 제곱의 합으로 바꿉니다.
숫자가 1이 될 때까지 과정을 반복하거나(그 값이 머무를 위치) 1을 포함하지 않는 주기에서 끝없이 반복합니다.
이 프로세스가 1로 끝나는 숫자는 행복합니다.
n이 행복한 숫자이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

 

 

제약사항

• 1 <= n <= 2^31 - 1

---

Solution

문제를 풀 때 고려한 사항

• n의 범위는 양의 정수인 int 범위이다.
• circle이 발생하는지 여부를 체크해야 한다. 

---

Solution1

가장 쉽게 생각할 수 있는 방법은 그냥 무작정 계산을 해보는 것이다.
circle 체크를 위해 map을 사용한다. 

 

class Solution {
public:
    bool isHappy(int n) {
        int sum = 0;
		map<int, bool> my_map; 
		
		while(1){
			while(n != 0){
				sum += ((n%10) * (n%10));
				n /= 10;
			}
			
			if(sum == 1) return true;
			if(my_map.find(sum) != my_map.end()) return false;
			
			my_map[sum] = true;
			n = sum;
			sum = 0;
		}
		
		return false; // not found
    }
};

• Time complexity : O(logn)
• Space Complexity : O(1)

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/815/

Explore - LeetCode