[LeetCode] 342. Power of Four

https://leetcode.com/problems/power-of-four/

Power of Four - LeetCode

Power of Four - Easy

 

주어진 정수 n이 4의 거듭제곱 으로 표현될 수 있는지 출력하는 문제다.

문제는 정말 상당히 쉽다. 1이 될때까지 n을 4로 계속 나눠주면 된다.

이 때, 나머지가 생기면 false가 된다.

 

근데 문제에서 도전 조건으로 준 것 중, loop와 recursive를 사용하지 않고 풀 수 있는지가 있었다.

이것은 도저히 고민하다가 다른사람들의 코드를 봐봤다.

대부분은 log를 사용했는데 너무 흔한방법이라 이걸까.. 생각을 했다.

그러다가 번뜩이는 아이디어를 봐서 공유한다.

출처는 아래 링크.

https://leetcode.com/problems/power-of-four/discuss/1530677/Simple-Maths100-faster5-lines-code

 

전체 풀이 코드

class Solution {
public:
    bool isPowerOfFour(int n) {return n>0 && ((!(1073741824 % n) && (n%10==4 || n%10==6)) || n==1);}
};

간단하고 신기하게 생겼다.

1073741824 는 4^15 로, int 범위에서 가장 큰 4의 거듭제곱 형태이다.

1073741824 는 고로 2^30 으로 소인수분해가 되어 1073741824 가 n으로 나눠진다면 n은 2의 거듭제곱이라는 말이 된다. 

2의 거듭제곱을 조금 써보면, 2, 4, 8, 16, 32, 64, 128, ... 가 되는데,

일의 자리수를 보면 2, 4, 8, 6, 2, 4, 8, 6, ... 이렇게 반복이 된다.4의 거듭제곱 자리는 일의 자리가 4와 6이 나오는 것을 알 수 있고,2의 거듭제곱은 2와 8이 나오게 된다.이를 이용해 n의 일의자리가 4 또는 6이라면 4의 거듭제곱이 되는 것이다.

 

게시글 제목처럼 간단한 수학이지만 아이디어가 참 좋았다.