Log inSign up
easyLeetCodeNot Started

Power of Two

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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.

Could you solve it without loops or recursion in O(1) time?

Example 1 · Example 1: n = 1:

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

Example 2 · Example 2: n = 16:

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

Example 3 · Example 3: n = 3:

Input: n = 3
Output: false
Explanation: 3 cannot be represented as 2x for any integer x.

Constraints:

  • -231 <= n <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanics of binary decrement n - 1.
  • Prove why n & (n - 1) == 0 uniquely characterizes single-bit positive numbers.
  • Handle edge cases such as n <= 0 and integer overflow.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determine if n is 2x.
  • Constant-time validation without loops.
  • Fundamental bit trick used in sparse matrix and Fenwick tree designs.

Algorithmic Decision Tree:

  • Return n > 0 && (n & (n - 1)) == 0.

Connected Patterns:

Power of FourNumber of 1 BitsFind the Only Set Bit

1. Repeated Division by 2

Intuition

If n <= 0, return false. While n % 2 == 0, divide n /= 2. If n == 1, return true; else return false.

When to apply: Basic mathematical definition.

Algorithm

  1. Step 1: If n <= 0, return false.
  2. Step 2: While n % 2 == 0, n /= 2.
  3. Step 3: Return n == 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool isPowerOfTwoBrute(int n) {
6 if (n <= 0) return false;
7 while (n % 2 == 0) {
8 n /= 2;
9 }
10 return n == 1;
11}
12
13int main() {
14 cout << boolalpha;
15 cout << "Brute (1): " << isPowerOfTwoBrute(1) << endl; // true
16 cout << "Brute (16): " << isPowerOfTwoBrute(16) << endl; // true
17 cout << "Brute (3): " << isPowerOfTwoBrute(3) << endl; // false
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

2. Popcount Verification

Intuition

If n <= 0, return false. Count set bits using Brian Kernighan's method. If count is 1, return true; else false.

When to apply: When verifying bit patterns directly.

Algorithm

  1. Step 1: If n <= 0, return false.
  2. Step 2: Count set bits: while temp > 0, temp &= (temp - 1), count++.
  3. Step 3: Return count == 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool isPowerOfTwoPopcount(int n) {
6 if (n <= 0) return false;
7 int count = 0;
8 while (n > 0) {
9 n &= (n - 1);
10 count++;
11 }
12 return count == 1;
13}
14
15int main() {
16 cout << boolalpha;
17 cout << "Popcount (16): " << isPowerOfTwoPopcount(16) << endl; // true
18 cout << "Popcount (12): " << isPowerOfTwoPopcount(12) << endl; // false
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(k) <= 32
  • Space complexity: O(1)

3. Direct Bit Trick (n & (n - 1)) == 0

Intuition

If n <= 0, return false immediately. A positive integer n is a power of two if and only if (n & (n - 1)) == 0, because subtracting 1 toggles every bit from the lowest 1-bit downwards.

When to apply: Optimal canonical solution for power of two.

Algorithm

  1. Step 1: Return n > 0 && (n & (n - 1)) == 0.

Bit Trick Trace for n = 16 and n = 12

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Case 1 (n = 16): 16 is 10000_2, 16 - 1 = 15 is 01111_2
Visual state
Values and pointers at this exact step
pointers
S
0
0
↑ true
Check / comparison
16 & 15 == 0
Decision / next transition
Valid power of two.
Why this step matters

Case 1 (n = 16): 16 is 10000_2, 16 - 1 = 15 is 01111_2. 16 & 15 = 00000_2 = 0. Positivity test 16 > 0 is true. Result: true.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 bool isPowerOfTwo(int n) {
8 return n > 0 && (n & (n - 1)) == 0;
9 }
10};
11
12int main() {
13 Solution sol;
14 cout << boolalpha;
15 cout << "Optimal (1): " << sol.isPowerOfTwo(1) << endl; // true
16 cout << "Optimal (16): " << sol.isPowerOfTwo(16) << endl; // true
17 cout << "Optimal (3): " << sol.isPowerOfTwo(3) << endl; // false
18 cout << "Optimal (-16): " << sol.isPowerOfTwo(-16) << endl; // false
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Repeated DivisionO(log n)O(1)While n > 0 and n % 2 == 0, divide n by 2. Return n == 1.Iterative division.
2.Better — Popcount / Brian KernighanO(k) <= 32O(1)If n <= 0 return false; count 1-bits and return count == 1.Popcount routine.
3.Optimal — Direct Bit TrickOptimalO(1)O(1)Return n > 0 && (n & (n - 1)) == 0.Zero latency.

Common Pitfalls & Crucial Edge Cases

Forgetting `n > 0`

Fails on 0 and negative powers of two.

Operator precedence

n & n - 1 == 0 evaluates as n & (n - 1 == 0) because == has higher precedence than &. Always write (n & (n - 1)) == 0.

Using loop division

While while (n % 2 == 0) n /= 2 works, it takes O(log n) time and is rejected when O(1) bit manipulation is requested.

Crucial Edge Cases to Validate:

  • n = 0 — Returns false.
  • Negative numbers (e.g. n = -16, n = -2147483648) — Powers of two must be strictly positive; returns false.
  • n = 1 (2^0) — Returns true.
  • n = INT_MIN (-2^31) — In two's complement, -2147483648 & -2147483649 can produce 0 if not guarded by n > 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Write the one-liner return n > 0 && (n & (n - 1)) == 0; and explain its mathematical basis immediately.
  2. Point out the operator precedence pitfall: == binds tighter than &.
  3. Mention that this condition is used throughout systems programming (e.g. ring buffer sizing, memory allocation alignment).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is n > 0 && (n & (n - 1)) == 0 a necessary and sufficient check for a power of two?

2.Why does n = 0 fail if only checking (n & (n - 1)) == 0 without n > 0?

3.What is the time complexity of the bitwise power of two check?

Back to DSA Sheet