[leetcode #231] Power of Two

Problem

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2ˣ.

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

Constraints:

・ -2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Idea

간단한 문제다. 주어진 수가 2의 제곱인지 판별하면 된다.

0보다 같거나 작으면 2의 제곱일 수 없으므로 곧바로 false를 리턴한다. 그 외 경우는 1이 나올 때까지 2로 나누다가 나머지가 0이 아닐 경우 false를 리턴하면 된다. 마지막으로 1이 나왔을 경우 true를 리턴한다.

Solution

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0)
            return false;

        while (n > 1) {
            if (n % 2 != 0)
                return false;
            n = n / 2;
        }

        return true;
    }
}

사실 훨씬 쉽게 푸는 방법이 있다. 그건 바로...

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && Integer.bitCount(n) == 1;
    }
}

bit count가 1개인 것만 체크하면 Follow up에 나온 것처럼 recursion 없이 풀 수 있다. =_=

Reference

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