11.10 Power of Two

11.10.1 Problem Metadata

11.10.2 Description

Determine whether a positive integer n is a power of two.

11.10.3 Examples

Input: 5
Output: false

Input: 8
Output: true

11.10.4 Constraints

  • 0 <= n <= 2^31 - 1

11.10.5 Solution 1 - Recursive Halving

11.10.5.1 Walkthrough

Repeatedly divide n by 2 as long as it is even. If we reach 1, n is a power of two; if we encounter an odd number (other than 1) or zero, it is not.

11.10.5.2 Analysis

  • Time Complexity: O(log n)
  • Space Complexity: O(log n) recursion depth

11.10.5.3 Implementation Steps

  1. Handle n <= 0 as false.
  2. Base case n == 1 is true.
  3. If n is odd, return false.
  4. Recurse on n / 2.

11.10.5.4 Code - Java

public boolean isPowerOfTwoRecursive(int n) {
    if (n <= 0) {
        return false;
    }
    if (n == 1) {
        return true;
    }
    if ((n & 1) == 1) {
        return false;
    }
    return isPowerOfTwoRecursive(n / 2);
}

11.10.6 Solution 2 - Bitwise Trick

11.10.6.1 Walkthrough

Power of two numbers have a single bit set. Checking n & (n - 1) clears the lowest set bit; for powers of two, the result is zero.

11.10.6.2 Analysis

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

11.10.6.3 Code - Java

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