logo
Leetcode
HackerRank
Love Babbar
Interview Prep
Cheat Sheet
Dynamic Sheet
About Us
Back to Bit Manipulation

Power of Two

MediumLeetCode Link
Source Repo

Power of Two

šŸ§© 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.

šŸ”¹ Example 1:

Input:

n = 1

Output:

true

šŸ”¹ Example 2:

Input:

n = 16

Output:

true

šŸ”¹ Example 3:

Input:

n = 3

Output:

false

šŸ” Approaches

1. Bitwise Trick ($(N \ & \ (N - 1)) == 0$)

  • Concept:
  • Powers of two in binary are 1 followed by 0s (e.g., 100, 1000).
  • N - 1 flips the rightmost 1 and all bits to its right (e.g., 100 - 1 = 011).
  • N & (N - 1) removes the rightmost set bit.
  • Logic: A power of two has exactly one bit set. Removing it should result in 0.
  • Constraints: n must be positive.
  • Check: n > 0 AND (n & (n - 1)) == 0.

2. Iterative/Recursive Division

  • Concept: Keep dividing n by 2 while n % 2 == 0. If you reach 1, it's a power of two.
  • Complexity: $O(\log n)$. Bitwise is $O(1)$.

ā³ Time & Space Complexity

  • Time Complexity: $O(1)$.
  • Space Complexity: $O(1)$.

šŸš€ Code Implementations

C++

class Solution {
public:
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
// Use long long to prevent potential overflow issues in general, 
// though n & (n-1) is safe for positive int
return (n & (n - 1ll)) == 0;
}
};

Python

class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
return (n & (n - 1)) == 0

Java

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

šŸŒ Real-World Analogy

Specific Measurements:

A standard measuring cup set has sizes that are powers (or halves) of each other. A power of two is like having a container that exactly matches one of the binary standard sizes without needing to combine multiple sizes.

šŸŽÆ Summary

āœ… Bit Manipulation Basic: n & (n - 1) clears the lowest set bit. If the result is 0, there was only 1 bit set.

Solution Code
O(n) TimeO(1) Space
#include <iostream>

using namespace std;

class Solution {
public:
  bool isPowerOfTwo(int n) {
    if (n <= 0)
      return false;
    // Cast to long long literal 1ll to ensure subtraction promotion handles
    // cases correctly if passed roughly or just to match implementation
    // pattern. For standard int, n-1 is fine.
    return (n & (long long)n - 1) == 0;
  }
};

int main() {
  Solution sol;
  cout << boolalpha;
  cout << "Test Case 1 (1): " << sol.isPowerOfTwo(1) << endl;   // true
  cout << "Test Case 2 (16): " << sol.isPowerOfTwo(16) << endl; // true
  cout << "Test Case 3 (3): " << sol.isPowerOfTwo(3) << endl;   // false
  return 0;
}
SYSTEM STABLEUTF-8 ā€¢ STATIC_RENDER