Power of Two

Easy
154.

Power of Two

EasyMathBit ManipulationAmazonGoogleAppleZohoSnapchat

Power of Two is an easy coding problem on math and bit manipulation, asked in Amazon, Google, Zoho and Apple interviews.

Given an integer n, return true if it is a power of two — that is, if there exists an integer x with 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 <= n <= 2^31 - 1

Follow-up: Can you solve it without loops or recursion?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Power of Two — Solution in Python, Java & C++

Power of Two solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.

Power of Two is an easy coding problem on math and bit manipulation, asked in Amazon, Google, Zoho and Apple interviews.

Problem statement

Given an integer n, return true if it is a power of two — that is, if there exists an integer x with 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 <= n <= 2^31 - 1

Follow-up: Can you solve it without loops or recursion?

Hints for Power of Two

  1. Hint 1

    Powers of two are positive; rule out zero and negatives first.

  2. Hint 2

    In binary a power of two has exactly one set bit.

  3. Hint 3

    n & (n - 1) clears the lowest set bit. If that leaves zero, there was only one bit to clear.

How to solve Power of Two

A positive power of two has exactly one set bit, and n & (n - 1) clears the lowest set bit — so the result is zero only when there was nothing else.

Approach

  1. Return false for n <= 0.
  2. Return (n & (n - 1)) == 0.

Why it works

Subtracting one flips the lowest set bit to zero and every bit below it to one, leaving higher bits untouched. ANDing with the original therefore erases exactly the lowest set bit. If n had a single bit the result is zero; with two or more bits, the higher ones survive.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • 0 & -1 == 0, so without the positivity check zero is misreported as a power of two.
  • Negative numbers fail the same guard; -2^31 has a single bit in two's complement but is not 2^x for any integer x.

Reference solution

Python

def isPowerOfTwo(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

Java

public static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

C++

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

JavaScript

var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n - 1)) === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation