Power of Two

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 == 2x.

Example 1:

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

Example 2:

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

Example 3:

Input: n = 3 Output: false

Constraints:

• -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

Approach: n & (n - 1) Bit Manipulation (Optimal Solution)

Algorithm

1. A power of two has exactly one 1 bit in its binary representation
2. For any power of two, n & (n - 1) equals 0
3. Also require n > 0 to reject 0 and negative values

Time & Space Complexity

• Time Complexity: O(1) - constant time, no loops
• Space Complexity: O(1) - constant extra space

Java Implementation

public class PowerOfTwo {

    /**
     * Determine whether n is a power of two.
     * @param n Input integer (can be negative or zero)
     * @return true if n is a power of two
     */
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 1");
        System.out.println("Output: " + isPowerOfTwo(1)); // Expected: true

        System.out.println("Input: n = 16");
        System.out.println("Output: " + isPowerOfTwo(16)); // Expected: true

        System.out.println("Input: n = 3");
        System.out.println("Output: " + isPowerOfTwo(3)); // Expected: false
    }
}

Alternative Approach: Loop Division

public class PowerOfTwoLoop {

    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        return n == 1;
    }
}

Example Walkthrough

For n = 16 (binary 10000):

• n & (n - 1) = 10000 & 01111 = 00000 = 0, and n > 0, so return true.

For n = 3 (binary 11):

• n & (n - 1) = 11 & 10 = 10 != 0, so return false.

Key Points

1. Single Set Bit: Powers of two have exactly one 1 bit
2. Bit Trick: n & (n - 1) clears the lowest set bit; it is 0 only for powers of two
3. Positive Check: n > 0 rejects zero and negative numbers (note -2147483648 passes n & (n-1) == 0)
4. No Loops: The follow-up is satisfied with a constant-time check
5. Loop Alternative: Repeated division is correct but O(log n)