(LeetCode) 202. Happy Number
202. Happy Number
- Explore : Interview > Top Interveiw Questions > Medium Collection
- 분류 : Math
- 난이도 : Easy
Problem
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 1
1
2
3
4
5
6
7
| Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
|
Example 2
1
2
| Input: n = 2
Output: false
|
Constraints
Solution
Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
fun isHappy(n: Int): Boolean {
var number = n
while (true) {
if (number == 1 || number == 7) {
return true
} else if (number == 4) {
return false
}
var temp = 0
while (number > 0) {
temp += (number % 10) * (number % 10)
number /= 10
}
number = temp
}
}
}
|
Point of Thinking
- 주어진 규칙대로 계속 반복하다가 1과 7일 나오면 true, 4가 나오면 false를 반환하면 Accepted.
- 이게 왜 Math 문제인고 하니.. 숫자의 반복을 통한 규칙성이 있기때문이다.
- 결국 문제는 1이면 Happy Number인 것이므로 1은 무조건 true임을 유추할 수 있다.
- 이를 토대로 1부터 9까지 반복하게 되면…
for (n in 1 .. 9)
1
2
3
4
| Input: n = 2
Output: false
Explanation:
2^2 = 4
|
연산을 반복하다가 2가 주어질 경우, 2^2는 4이므로 4가 주어졌을 때와 와 동일한 결과를 낼 것이다.
4를 보기전에 3부터 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Input: n = 3
Output: false
Explanation:
3^2 = 9
9^2 = 81
8^2 + 1^2 = 64 + 1 = 65
6^2 + 5^2 = 36 + 25 = 61
6^2 + 1^2 = 36 + 1 = 37
3^2 + 7^2 = 9 + 49 = 58
5^2 + 8^2 = 25 + 64 = 89
8^2 + 9^2 = 64 + 81 = 145
1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
4^2 + 2^2 = 16 + 4 = 20
2^2 = 4
|
n이 3으로 주어지면 결국 4로 귀결된다.
즉 n이 2일 경우, 3일 경우, 4일 경우 모두 동일한 결과값을 보이게 된다.
이제 4를 보자.
1
2
3
4
5
6
7
8
9
10
11
| Input: n = 4
Output: false
Explanation:
4^2 = 16
1^2 + 6^2 = 1 + 36 = 37
3^2 + 7^2 = 9 + 49 = 58
5^2 + 8^2 = 25 + 64 = 89
8^2 + 9^2 = 64 + 81 = 145
1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
4^2 + 2^2 = 16 + 4 = 20
2^2 = 4
|
n이 4인 경우에는 영원히 끝나지않고 반복하게 된다.
즉 1이 될 수가 없으므로 n이 4인 경우엔 false를 반환하도록 처리한다.
1
2
3
4
5
6
7
8
9
10
11
| Input: n = 5
Output: false
Explanation:
5^2 = 25
2^2 + 5^2 = 4 + 25 = 29
2^2 + 9^2 = 4 + 81 = 85
8^2 + 5^2 = 64 + 25 = 89
8^2 + 9^2 = 64 + 81 = 145
1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
4^2 + 2^2 = 16 + 4 = 20
2^2 = 4
|
n이 5일때도 4로 귀결된다.
1
2
3
4
5
6
7
8
9
| Input: n = 6
Output: false
Explanation:
6^2 = 36
3^2 + 6^2 = 9 + 36 = 45
4^2 + 5^2 = 16 + 25 = 41
4^2 + 1^2 = 16 + 1 = 17
1^2 + 7^2 = 1 + 49 = 50
5
|
n이 6일 경우 연산 과정에서 5로 바뀌게되고, 이는 결국 4로 바뀌게 된다.
1
2
3
4
5
6
7
8
| Input: n = 7
Output: true
Explanation:
7^2 = 49
4^2 + 9^2 = 16 + 81 = 97
9^2 + 7^2 = 81 + 49 = 130
1^2 + 3^2 = 1 + 9 = 10
1
|
n이 7인 경우는 1로 귀결되므로 Happy Number가 된다.
1
2
3
4
5
6
7
8
9
10
11
12
| Input: n = 8
Output: false
Explanation:
8^2 = 64
6^2 + 4^2 = 36 + 16 = 52
5^2 + 2^2 = 25 + 4 = 29
2^2 + 9^2 = 4 + 81 = 85
8^2 + 5^2 = 64 + 25 = 89
8^2 + 9^2 = 64 + 81 = 145
1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
4^2 + 2^2 = 16 + 4 = 20
2^2 = 4
|
n이 8일 경우엔 4로 귀결된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| Input: n = 9
Output: false
Explanation:
9^2 = 81
8^2 + 1^2 = 64 + 1 = 65
6^2 + 5^2 = 36 + 25 = 61
6^2 + 1^2 = 36 + 1 = 37
3^2 + 7^2 = 9 + 49 = 58
5^2 + 8^2 = 25 + 64 = 89
8^2 + 9^2 = 64 + 81 = 145
1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
4^2 + 2^2 = 16 + 4 = 20
2^2 = 4
|
n이 9일 경우도 결국 4로 귀결된다.
즉, Happy Number를 구하기 위한 연산을 계속해서 반복하면서 1이나 7이 되는 경우엔 true, 4가 나오는 경우엔 false를 반환하면 된다.
