algoadvance

Leetcode 231. Power of Two

Problem Statement

Determine if a given integer ( n ) is a power of two. A number is considered a power of two if it can be expressed as ( 2^k ) where ( k ) is a non-negative integer.

Clarifying Questions

1. Constraints on Input:
   • Is ( n ) always an integer?
     • Yes, ( n ) is always an integer.
   • Can ( n ) be negative or zero?
     • Yes, ( n ) can be any integer which includes negative numbers and zero.
2. Expected Output:
   • Should the function return a boolean value?
     • Yes, the function should return true if ( n ) is a power of two, otherwise return false.
3. Efficiency Constraints:
   • Is there a preferred time complexity?
     • Aim for an efficient solution, ideally O(1).

Strategy

To determine if ( n ) is a power of two, we can utilize the properties of binary representation of powers of two:

• A power of two in binary form has exactly one ‘1’ bit and the rest are ‘0’s. For example, 1 (2^0), 2 (2^1), 4 (2^2), 8 (2^3) are 1, 10, 100, and 1000 in binary respectively.

  One efficient way to leverage this property is using a bitwise AND operation. For a binary number that represents a power of two:

  • ( n ) & (n - 1) should be 0. This is because ( n ) has exactly one ‘1’ bit in its binary representation and ( n-1 ) will have all bits flipped after that ‘1’ bit is the first ‘0’.

• Additionally, ( n ) should be greater than 0.

Code

public class Solution {
    public boolean isPowerOfTwo(int n) {
        // If n is less than or equal to 0, it can't be a power of two
        if (n <= 0) {
            return false;
        }
        
        // Check if n is a power of two using the bitwise trick
        return (n & (n - 1)) == 0;
    }
}

Explanation

1. Initial Check:
   • We first check if ( n ) is less than or equal to 0. If it is, return false because a power of two must be a positive number.
2. Bitwise Check:
   • Perform ( n \& (n - 1) ) and check if the result is 0.
   • This works because if ( n ) is a power of two, its binary representation has a single ‘1’ bit followed by zeros. ( n-1 ) flips all bits after the ‘1’ bit, so ( n \& (n-1) ) should be zero.

Time Complexity

• The time complexity is O(1) because both the check for ( n ) being less than or equal to 0 and the bitwise operation ( n \& (n - 1) ) are constant-time operations.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?