Jobs

Interviews

Discussions

Power of Two

Easy

Asked by:

More companies

24 views

Topics:

Bit Manipulation

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⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Try coding it in LeetCode

Power of Two

Easy

Asked by:

More companies

24 views

Topics:

Bit Manipulation

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⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer 'n'? Could 'n' be negative or zero?
Should I assume that 'n' is always an integer, or could it be a floating-point number?
Are there any specific constraints or limitations on the size of 'n' that I should be aware of?
If 'n' is not a power of two, should I return false, or is there any other specific value I should return?
Is there an expected behavior for extremely large values of 'n' that might cause overflow issues?

Brute Force Solution

Approach

The brute force approach to checking if a number is a power of two involves testing different powers of two. We essentially keep multiplying 2 by itself and see if we ever reach the target number. If we do, it's a power of two; if we pass it, it's not.

Here's how the algorithm would work step-by-step:

Start with the number 1, since 2 to the power of 0 is 1.
Compare this number to the given input number.
If they are equal, then the input number is a power of two, and we are done.
If the current number is larger than the input number, the input is NOT a power of two and we can stop.
If the current number is smaller, multiply the current number by 2.
Repeat the comparison and multiplication until either the numbers are equal (meaning it's a power of two) or the current number becomes greater than the input (meaning it's not a power of two).

Code Implementation

def is_power_of_two_brute_force(number):
    power_of_two = 1

    # Start with 2^0 = 1

    while True:
        if power_of_two == number:

            # We found the number so it is a power of two
            return True

        if power_of_two > number:

            # The power of two is greater than input
            return False

        # Multiply the power of two by two
        power_of_two *= 2

Big(O) Analysis

Time Complexity

O(log n) – The algorithm repeatedly multiplies a number by 2 until it either equals or exceeds the input number n. The number of multiplications is proportional to the exponent needed to reach n from 1 when 2 is the base. This is equivalent to the base-2 logarithm of n. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm uses a single variable to store the current power of 2 being tested. No other data structures are used that scale with the input number N. Therefore, the auxiliary space required is constant and independent of the input, resulting in O(1) space complexity.

Optimal Solution

Approach

The trick to this problem is understanding how numbers that are powers of two are represented in binary. We can then use a bitwise operation to quickly check if a number is a power of two without repeatedly dividing or using logarithms.

Here's how the algorithm would work step-by-step:

Subtract one from the given number.
Perform a bitwise AND operation between the original number and the result of the subtraction.
If the result of the bitwise AND is zero, then the original number is a power of two. Otherwise, it is not.

Code Implementation

def is_power_of_two(number):
    if number <= 0:
        return False

    # Subtract 1 from the number.
    number_minus_one = number - 1

    # Perform a bitwise AND to check power of 2.
    bitwise_and_result = number & number_minus_one

    # If the result is 0, it's a power of 2.
    if bitwise_and_result == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(1) – The algorithm performs a fixed number of bitwise operations (subtracting one and a bitwise AND). These operations take a constant amount of time regardless of the input number 'n'. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm only uses a single integer variable to store the result of the subtraction and bitwise AND operation. No additional data structures or variables are allocated based on the input number N. Therefore, the space required remains constant regardless of the size of the input, resulting in O(1) auxiliary space.

Edge Cases

Case	How to Handle
Input is zero	Return false because zero is not a power of two.
Input is a negative number	Return false because negative numbers are not powers of two.
Input is one	Return true because 2^0 = 1, so 1 is a power of two.
Input is a large positive integer (potential overflow)	Ensure the algorithm avoids potential integer overflows by using appropriate data types or bitwise operations (e.g., n > 0 && (n & (n - 1)) == 0).
Input is a very small positive number close to zero (potential floating-point errors if logarithms are used)	Avoid using logarithms to prevent potential floating-point inaccuracies.
Maximum integer value (Integer.MAX_VALUE)	Check if Integer.MAX_VALUE is a power of 2 and return true if it is, false otherwise.
Input is a non-integer	The problem specifies an integer input; handle this by either casting the input to an integer and proceeding, or throwing an IllegalArgumentException.
Multiple of a power of two, but not a power of two itself (e.g. 6)	The bitwise operation `n & (n - 1)` correctly identifies if a number is not a power of two.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer 'n'? Could 'n' be negative or zero?
Should I assume that 'n' is always an integer, or could it be a floating-point number?
Are there any specific constraints or limitations on the size of 'n' that I should be aware of?
If 'n' is not a power of two, should I return false, or is there any other specific value I should return?
Is there an expected behavior for extremely large values of 'n' that might cause overflow issues?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1, since 2 to the power of 0 is 1.
Compare this number to the given input number.
If they are equal, then the input number is a power of two, and we are done.
If the current number is larger than the input number, the input is NOT a power of two and we can stop.
If the current number is smaller, multiply the current number by 2.
Repeat the comparison and multiplication until either the numbers are equal (meaning it's a power of two) or the current number becomes greater than the input (meaning it's not a power of two).

Code Implementation

def is_power_of_two_brute_force(number):
    power_of_two = 1

    # Start with 2^0 = 1

    while True:
        if power_of_two == number:

            # We found the number so it is a power of two
            return True

        if power_of_two > number:

            # The power of two is greater than input
            return False

        # Multiply the power of two by two
        power_of_two *= 2

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Subtract one from the given number.
Perform a bitwise AND operation between the original number and the result of the subtraction.
If the result of the bitwise AND is zero, then the original number is a power of two. Otherwise, it is not.

Code Implementation

def is_power_of_two(number):
    if number <= 0:
        return False

    # Subtract 1 from the number.
    number_minus_one = number - 1

    # Perform a bitwise AND to check power of 2.
    bitwise_and_result = number & number_minus_one

    # If the result is 0, it's a power of 2.
    if bitwise_and_result == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return false because zero is not a power of two.
Input is a negative number	Return false because negative numbers are not powers of two.
Input is one	Return true because 2^0 = 1, so 1 is a power of two.
Input is a large positive integer (potential overflow)	Ensure the algorithm avoids potential integer overflows by using appropriate data types or bitwise operations (e.g., n > 0 && (n & (n - 1)) == 0).
Input is a very small positive number close to zero (potential floating-point errors if logarithms are used)	Avoid using logarithms to prevent potential floating-point inaccuracies.
Maximum integer value (Integer.MAX_VALUE)	Check if Integer.MAX_VALUE is a power of 2 and return true if it is, false otherwise.
Input is a non-integer	The problem specifies an integer input; handle this by either casting the input to an integer and proceeding, or throwing an IllegalArgumentException.
Multiple of a power of two, but not a power of two itself (e.g. 6)	The bitwise operation `n & (n - 1)` correctly identifies if a number is not a power of two.