231. Power of Two
easyCheck whether an integer is a power of two. The textbook bit-trick: a positive integer is a power of two if and only if n & (n - 1) is zero.
By Sam K., Founder, InterviewChamp.AI · Last verified
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^x.
Constraints
-2^31 <= n <= 2^31 - 1
Examples
Example 1
n = 1trueExplanation: 2^0 = 1
Example 2
n = 16trueExplanation: 2^4 = 16
Example 3
n = 3falseSolve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Powers of two in binary have exactly one set bit. Anything else has zero or two-plus.
Hint 2
n & (n - 1) clears the lowest set bit. If n has exactly one set bit, the result is 0.
Hint 3
Don't forget the n > 0 check — n = 0 and negative numbers should return false.
Solution approach
Reveal approach
One-line trick. Return n > 0 && (n & (n - 1)) == 0. The first conjunct rejects zero and negatives (which the constraints allow). The second exploits that powers of two have a single set bit, so n - 1 flips that bit to zero and turns every lower bit into one — AND'ing gives zero. Any other positive number has at least two set bits and one will survive the AND. O(1) time, O(1) space.
Complexity
- Time
- O(1)
- Space
- O(1)
Related patterns
- bit-manipulation
Related problems
- 326. Power of Three
- 342. Power of Four
- 191. Number of 1 Bits
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Apple
More Bit Manipulation practice problems
- 29. Divide Two Integers
- 78. Subsets
- 89. Gray Code
- 136. Single Number
- 137. Single Number II
- 187. Repeated DNA Sequences
- 190. Reverse Bits
- 191. Number of 1 Bits