231. Power of Two

Description

The problem requires checking whether a given integer n is a power of two. A number is a power of two if it can be expressed as 2^k where k is a non-negative integer. For example, 1 (2^0), 2 (2^1), 4 (2^2), 8 (2^3), etc., are all powers of two.

Intuition

A power of two has only one bit set in its binary representation (e.g., 1, 2, 4, 8 are 0001, 0010, 0100, 1000 in binary, respectively). Therefore, one intuitive way to check if a number is a power of two is to iterate through the powers of two and compare each with n.

Approach

1. Iterative Comparison: - Iterate through the first 31 powers of two, since 2^30 is the largest power of two within the range of a 32-bit signed integer. - For each power of two, compare it with n. - If any power of two matches n, return true. - If none match, return false.
2. Edge Cases: - Consider special cases like n = 0 (which is not a power of two) and negative numbers, which are also not powers of two.

Complexity

Time Complexity:

O(1). The loop runs a fixed number of iterations (31 iterations for a 32-bit integer), so the time complexity is constant.

Space Complexity:

O(1). The algorithm uses a fixed amount of extra space, regardless of the input size.

Code

C++

class Solution {
public:
    bool isPowerOfTwo(int n) {
        for (int i = 0; i < 31; i++) {
            if (pow(2, i) == n) {
                return true;
            }
        }
        return false;
    }
};

Python

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        for i in range(31):
            if 2 ** i == n:
                return True
        return False

Java

class Solution {
    public boolean isPowerOfTwo(int n) {
        for (int i = 0; i < 31; i++) {
            if (Math.pow(2, i) == n) {
                return true;
            }
        }
        return false;
    }

    // Usage Example
    public static void main(String[] args) {
        Solution sol = new Solution();
        boolean result = sol.isPowerOfTwo(16); // Example input
        System.out.println(result); // Output: true
    }
}

JavaScript

var isPowerOfTwo = function (n) {

    for (i = 0; i < 31; i++) {
        if (Math.pow(2, i) == n) {
            return true
        }
    }
    return false
};