Problem: Check if a Number is a 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 == 2^x.

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:

• n is a positive integer.

Approach:

A number n is a power of two if and only if it has exactly one bit set in its binary representation. For example:

• 1 (binary 0001) is 2^0
• 2 (binary 0010) is 2^1
• 4 (binary 0100) is 2^2
• 8 (binary 1000) is 2^3

Using the property that for any power of two, n & (n - 1) will be 0, we can check if the number is a power of two.

C Code:

#include <stdio.h>
#include <stdbool.h>

bool isPowerOfTwo(int n) {
    // Check if n is greater than 0 and if n & (n - 1) is 0
    return (n > 0) && (n & (n - 1)) == 0;
}

int main() {
    int n;
    printf("Enter an integer: ");
    scanf("%d", &n);

    if (isPowerOfTwo(n)) {
        printf("%d is a power of two.n", n);
    } else {
        printf("%d is not a power of two.n", n);
    }

    return 0;
}

Explanation:

• n & (n - 1): This bitwise operation works because for any power of two, its binary representation has only one bit set to 1. Subtracting 1 from a power of two flips all the bits after the most significant 1, and the & operation results in 0.

  • For example:
    • n = 16 (binary 10000), n - 1 = 15 (binary 01111), so 16 & 15 = 0.
    • n = 8 (binary 1000), n - 1 = 7 (binary 0111), so 8 & 7 = 0.

• Check: The function first ensures that n > 0 because negative numbers or zero can’t be powers of two. Then, it checks if the bitwise operation returns 0, which confirms that n is a power of two.

Time Complexity:

• The time complexity of this solution is O(1) because the bitwise operations are constant-time operations.

Example Output:

Input:

Enter an integer: 16

Output:

16 is a power of two.