[LeetCode] - 231. Power of Two

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Power of Two" 문제입니다.

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

 

문제 :

Given an integer n, return true if it is a power of two. Otherwise, return false. An in teger n is a power of two, if there exists an integer x such that n == 2^x.

---

Example 1 :

Input : n = 1

Output : true

Explanation : \( 2^0 = 1 \)

 

Example 2 :

Input : n = 16

Output : true

Explanation : \( 2^4 = 16 \)

 

Example 3 :

Input : n = 3

Output : false

 

Constraints : \( -2^{31} \leq n \leq 2^{31} - 1 \)

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

---

 

이 문제는 주어진 정수 \( n \)이 2의 거듭제곱인지 판별하는 함수를 작성하세요. 그렇다면 true를 반환하고, 그렇지 않다면 false를 반환하세요. 정수 \( n \)이 2의 거듭제곱이 되려면, 정수 \( x \)가 존재하여 \( n = 2^x \)가 되어야 합니다. 한국어로 간단히 설명하자면, 이 문제는 주어진 정수가 2의 거듭제곱인지 여부를 판별하는 함수를 작성하라고 요구합니다. 저는 우선 자바로 이 문제를 접근했습니다. 이 문제는 접근방식이 여러 가지 있습니다 하나씩 보여드리겠습니다 :

 

1. 비트 이동 연산을 이용한 2의 거듭제곱 판별

public class Solution {
    public boolean isPowerOfTwo(int n) {
        for (int i = 0; i < 31; i++) {
            if ((1 << i) == n) {
                return true;
            }
        }
        return false;
    }
}

 

위 코드에서는 2의 거듭제곱인지 확인하기 위해 for 루프를 사용합니다. 자세한 설명은 다음과 같습니다:

1. for 루프 초기화 및 조건 설정:
   • for (int i = 0; i < 31; i++)에서 루프는 0부터 30까지 반복됩니다. 이는 32비트 정수의 범위 내에서 2의 거듭제곱을 모두 검사하기 위함입니다.
2. 비트 이동 연산을 사용한 2의 거듭제곱 계산:
   • (1 << i)는 1을 왼쪽으로 i비트 이동시키는 연산으로, 이는 2i2^i2i와 같습니다. 예를 들어, i가 0일 때는 20=12^0 = 120=1, i가 1일 때는 21=22^1 = 221=2, i가 2일 때는 22=42^2 = 422=4가 됩니다.
3. 2의 거듭제곱 비교:
   • if ((1 << i) == n)에서 계산된 2i2^i2i 값이 주어진 정수 n과 같다면, n은 2의 거듭제곱이므로 true를 반환합니다.
4. 루프가 끝난 후 false 반환:
   • 루프가 끝날 때까지 2의 거듭제곱을 찾지 못하면, n은 2의 거듭제곱이 아니므로 false를 반환합니다.

---

2. 비트 연산을 이용한 2의 거듭제곱 판별

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

 

위와 같이, 주어진 정수가 2의 거듭제곱인지 확인하는 방법은 n이 0보다 작거나 같은 경우 false를 반환하고, 그렇지 않은 경우 n & (n - 1)이 0인지 확인합니다. 이 방법은 2의 거듭제곱인 경우에만 해당 비트 연산이 0을 반환하기 때문에 유효합니다. 최종적으로 주어진 정수가 2의 거듭제곱인 경우 true를, 그렇지 않은 경우 false를 반환합니다.

---

 

3. 로그 이용

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        double logResult = Math.log(n) / Math.log(2);
        double epsilon = 1e-10; // 매우 작은 허용 오차
        return Math.abs(logResult - Math.round(logResult)) < epsilon;
    }
}

 

이 코드에서는 주어진 정수 n이 2의 거듭제곱인지 여부를 확인하기 위해 로그 함수를 사용하고 있습니다. epsilon을 넣은 까닭은 부동 소수점 오차를 피하기 위해서입니다. 로그 계산 후 근사값을 정수로 비교하는 방식 대신, 작은 허용 오차를 사용하여 값을 비교하는 방법을 사용할 수 있습니다. (안 그러면 테스트 하나가 패스를 안 하더라고요)

---

각각 코드들의 Runtime 결과. 어차피 다 비슷함.