algoadvance

Leetcode 231. Power of Two

Problem Statement

  1. Power of Two

Given an integer n, write a function to determine if it is a power of two.

Clarifying Questions

  1. Input Range: What is the range of the input integer n?
    • Typical Response: The input can range from (-2^{31}) to (2^{31} - 1).
  2. Handling Negative Numbers: Should we consider negative numbers?
    • Typical Response: A negative number cannot be a power of two.
  3. Specific Examples: Can you provide some examples?
    • Typical Response:
      • Input: n = 1, Output: true (since (2^0 = 1))
      • Input: n = 16, Output: true (since (2^4 = 16))
      • Input: n = 3, Output: false (since 3 is not a power of two)
      • Input: n = -16, Output: false (negative numbers are not powers of two)

Strategy

To determine if n is a power of two, we can use the following properties:

  1. A power of two has exactly one 1 bit in its binary representation.
  2. For a number n that is a power of two, ( n ) and ( n-1 ) have no common set bits. Hence n & (n-1) == 0.

Given these properties:

  1. We can return false if n is less than or equal to zero.
  2. Otherwise, we check if n & (n-1) is zero.

Code

#include <iostream>

bool isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

// Example usage:
int main() {
    int testCases[] = {1, 16, 3, -16, 1024};
    for (int n : testCases) {
        std::cout << "isPowerOfTwo(" << n << ") = " << (isPowerOfTwo(n) ? "true" : "false") << std::endl;
    }
    return 0;
}

Time Complexity

This solution efficiently checks whether the given number is a power of two, adhering to both time and space constraints expected in competitive programming.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI