Jobs

Interviews

Discussions

Power of Four

Easy

Apple

1 view

Topics:

Bit Manipulation

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

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

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

Power of Four

Easy

Apple

1 view

Topics:

Bit Manipulation

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

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

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

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:

Is the input always a 32-bit integer?
Can the input be negative or zero?
If the input is not a power of four, what value should I return?
Are there any constraints on the space complexity of my solution?
Is there a defined range for the input number, or is it bounded by the maximum integer value?

Brute Force Solution

Approach

To check if a number is a power of four using a brute force approach, we can simply keep dividing the number by four. If at any point the result is not a whole number, then the original number cannot be a power of four.

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

First, see if the number is bigger than zero.
If it's not bigger than zero, it can't be a power of four, so we are done.
If the number is one, it is a power of four, so we are done.
Now, keep dividing the number by four.
After each division, check if the result is a whole number.
If the result is a whole number, see if the result equals one. If it does, then the original number is a power of four.
If the result is not a whole number at any time, the original number is not a power of four.

Code Implementation

def is_power_of_four_brute_force(number):
    # Powers of four must be positive numbers
    if number <= 0:
        return False

    # Base Case
    if number == 1:
        return True

    current_number = number
    while True:
        current_number = current_number / 4.0

        # Check if the result of the division is a whole number
        if current_number == int(current_number):

            # If the whole number is 1, then we have a power of four
            if current_number == 1:
                return True
        else:
            # If it is not a whole number, then it is not a power of four
            return False

Big(O) Analysis

Time Complexity

O(log₄(n)) – The algorithm repeatedly divides the input number n by 4 until it becomes 1 or the division results in a non-integer value. The number of divisions performed is logarithmic with base 4, specifically log₄(n). The other operations within the loop (checking if the result is a whole number and comparing to 1) take constant time. Therefore, the time complexity is O(log₄(n)).

Space Complexity

O(1) – The provided algorithm operates by repeatedly dividing the input number by four and checking for a whole number result. It uses a constant amount of extra memory, primarily to store the current value of the number being divided. No auxiliary data structures like arrays, lists, or hash maps are created. Therefore, the space complexity is independent of the input number (N) and remains constant.

Optimal Solution

Approach

The key to efficiently determining if a number is a power of four is to realize powers of four are also powers of two. We can leverage this, along with a clever bit manipulation trick, to avoid iterative division. This helps determine the solution much faster.

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

First, check if the number is a power of two. Numbers that are powers of four must first satisfy this condition.
Next, consider that every power of four in binary representation has a single '1' bit, and it always appears in an odd position.
Use a bitwise trick that isolates the rightmost '1' bit and then checks that its location is at an odd numbered bit place.
If both the power of two check and the odd bit location are confirmed, then the number is a power of four.

Code Implementation

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

    # Power of 4 must also be a power of 2.
    is_power_of_two = (number & (number - 1)) == 0

    if not is_power_of_two:
        return False

    # Check if the '1' bit is in an odd position.
    # Powers of 4 have '1' at odd bit positions only.
    odd_position_check = number & 0x55555555

    if odd_position_check:
        return True
    
    return False

Big(O) Analysis

Time Complexity

O(1) – The provided solution relies on bitwise operations. Checking if a number is a power of two using `n & (n - 1)` takes constant time. The bit manipulation to check if the '1' bit is in an odd position also takes constant time, regardless of the input number's size. Therefore, the overall time complexity of the algorithm is O(1) because it involves a fixed number of operations.

Space Complexity

O(1) – The algorithm described only uses a few constant space variables for bitwise operations. There are no auxiliary data structures such as arrays, hash maps, or lists created. The amount of memory used does not scale with the input number N. Thus, the space complexity is constant.

Edge Cases

Case	How to Handle
Input is zero	Return false, as 0 is not a power of 4.
Input is negative	Return false, as powers of 4 are always positive.
Input is not an integer	If a float is passed, either cast it to an integer or return false, based on requirements (casting may lead to precision issues).
Input is 1	Return true, as 4^0 = 1.
Integer overflow if checking by repeated multiplication	Use bit manipulation or logarithmic approach to avoid potential overflow.
Input is a power of 2 but not a power of 4 (e.g., 2, 8)	Check if the number is a power of 2 and then verify if the set bit is at an even position to determine if it is a power of 4.
Maximum integer value (Integer.MAX_VALUE)	Check if Integer.MAX_VALUE is a power of 4; if not, the algorithm must handle it correctly without overflow or incorrect results.
Input close to zero but greater than zero (e.g., 0.00000001)	If the input is expected to be an integer, ensure that input checking for non-integer values are performed.

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:

Is the input always a 32-bit integer?
Can the input be negative or zero?
If the input is not a power of four, what value should I return?
Are there any constraints on the space complexity of my solution?
Is there a defined range for the input number, or is it bounded by the maximum integer value?

Brute Force Solution

Approach

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

First, see if the number is bigger than zero.
If it's not bigger than zero, it can't be a power of four, so we are done.
If the number is one, it is a power of four, so we are done.
Now, keep dividing the number by four.
After each division, check if the result is a whole number.
If the result is a whole number, see if the result equals one. If it does, then the original number is a power of four.
If the result is not a whole number at any time, the original number is not a power of four.

Code Implementation

def is_power_of_four_brute_force(number):
    # Powers of four must be positive numbers
    if number <= 0:
        return False

    # Base Case
    if number == 1:
        return True

    current_number = number
    while True:
        current_number = current_number / 4.0

        # Check if the result of the division is a whole number
        if current_number == int(current_number):

            # If the whole number is 1, then we have a power of four
            if current_number == 1:
                return True
        else:
            # If it is not a whole number, then it is not a power of four
            return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if the number is a power of two. Numbers that are powers of four must first satisfy this condition.
Next, consider that every power of four in binary representation has a single '1' bit, and it always appears in an odd position.
Use a bitwise trick that isolates the rightmost '1' bit and then checks that its location is at an odd numbered bit place.
If both the power of two check and the odd bit location are confirmed, then the number is a power of four.

Code Implementation

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

    # Power of 4 must also be a power of 2.
    is_power_of_two = (number & (number - 1)) == 0

    if not is_power_of_two:
        return False

    # Check if the '1' bit is in an odd position.
    # Powers of 4 have '1' at odd bit positions only.
    odd_position_check = number & 0x55555555

    if odd_position_check:
        return True
    
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return false, as 0 is not a power of 4.
Input is negative	Return false, as powers of 4 are always positive.
Input is not an integer	If a float is passed, either cast it to an integer or return false, based on requirements (casting may lead to precision issues).
Input is 1	Return true, as 4^0 = 1.
Integer overflow if checking by repeated multiplication	Use bit manipulation or logarithmic approach to avoid potential overflow.
Input is a power of 2 but not a power of 4 (e.g., 2, 8)	Check if the number is a power of 2 and then verify if the set bit is at an even position to determine if it is a power of 4.
Maximum integer value (Integer.MAX_VALUE)	Check if Integer.MAX_VALUE is a power of 4; if not, the algorithm must handle it correctly without overflow or incorrect results.
Input close to zero but greater than zero (e.g., 0.00000001)	If the input is expected to be an integer, ensure that input checking for non-integer values are performed.