[leetCode] 231. Power of Two

🔵 Description

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 == 2x.

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

Example 4:

Input: n = 4
Output: true

Example 5:

Input: n = 5
Output: false

🔵 Solution

power of two?

주어진 숫자 n이 2의 제곱으로 나타낼 수 있다면 true, 없다면 false를 리턴해주면 된다.

n이 2의 제곱이라면 비트 연산을 했을 때 앞자리 1을 제외한 나머지 자리는 0이다.
당연하게도 이진법으로 십진수를 변환할 때 각 자리는 2의 제곱이기 때문이다.

2 => 10
4 => 100
8 => 1000
16 => 10000

n-1은 반대로 맨 앞자리를 제외한 나머지만 1이된다.

2-1 => 01
4-1 => 011
8-1 => 0111
16-1 => 01111

따라서 n과 n-1을 &연산자로 비트 논리곱을 한다면 각 자릿수를 비교했을 때 공통적으로 0 이거나 1이지 않으므로 0이 리턴된다.

이 조건을 충족해야만 n이 2의 제곱수인 것이다.

🔵 Result

Runtime

85 ms, faster than 71.65% of JavaScript online submissions for Power of Two.

Memory Usage

40.1 MB, less than 65.86% of JavaScript online submissions for Power of Two.

Reference

• https://velog.io/@ansrjsdn/LeetCode-Power-Of-Two-JavaScript