Problem Overview

You are given an integer n. The task is to determine whether n is a power of two.
A number is a power of two if it can be expressed as 2^x, where x is a non-negative integer.

In other words:

• 1 is 2^0 → true
• 2 is 2^1 → true
• 4 is 2^2 → true
• 6 cannot be represented as 2^x → false

Example 1:

Input: n = 1
Output: true
Explanation: 2^0 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2^4 = 16

Example 3:

Input: n = 3
Output: false

Constraints:

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

---

Intuition / Approach

A number that is a power of two has a unique property in binary representation:
It has exactly one bit set to 1.

For example:

Decimal	Binary	Power of Two
1	0001	Yes
2	0010	Yes
4	0100	Yes
6	0110	No
8	1000	Yes

So, if a number is positive and has only one ‘1’ bit in its binary representation, it’s a power of two.

---

Key Observations

1. Negative numbers and zero cannot be powers of two.
2. For a power of two number n, n & (n - 1) equals 0.
   • Example: 8 (1000) and 7 (0111) → 1000 & 0111 = 0000
   • This works because subtracting 1 from a power of two flips the rightmost 1 and all bits after it.

---

Algorithm Steps

1. If n <= 0, return false.
2. Use the bitwise trick: check if (n & (n - 1)) == 0.
   • If true, return true; else, return false.

This is an O(1) constant-time solution.

---

Java Code Implementation

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

    public static void main(String[] args) {
        PowerOfTwo solution = new PowerOfTwo();
        System.out.println(solution.isPowerOfTwo(1));   // true
        System.out.println(solution.isPowerOfTwo(16));  // true
        System.out.println(solution.isPowerOfTwo(3));   // false
        System.out.println(solution.isPowerOfTwo(8));   // true
        System.out.println(solution.isPowerOfTwo(-4));  // false
    }
}

---

Step-by-Step Example

Let’s check whether n = 8 is a power of two.

n = 8 → binary = 1000
n - 1 = 7 → binary = 0111
n & (n - 1) = 1000 & 0111 = 0000

Since the result is 0, 8 is a power of two.

Now, for n = 10:

n = 10 → binary = 1010
n - 1 = 9  → binary = 1001
n & (n - 1) = 1010 & 1001 = 1000 (non-zero)

Hence, 10 is not a power of two.

---

Alternative Approach: Iterative Division

You can also check using division:

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

This approach repeatedly divides n by 2 until it becomes 1 or not divisible by 2.
It is correct but slower than the bitwise method because it involves multiple divisions.

---

Complexity Analysis

Time Complexity:

• Bitwise method: O(1) (only one operation)
• Division method: O(log n) (number of times n is divided by 2)

Space Complexity:

• O(1) for both methods since no extra space is used.

---

Alternative Approach: Using Built-in Function (Java 8+)

If you want to use built-in utilities, you can check the number of set bits in Java using:

return n > 0 && Integer.bitCount(n) == 1;

The bitCount() method returns the number of set bits in the binary representation of n.
If only one bit is set and n is positive, then it’s a power of two.