Jobs

Interviews

Discussions

Pow(x, n)

Medium

Google

2 views

Topics:

RecursionBit Manipulation

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ). This function should handle both positive and negative values of n.

For example:

If x = 2.00000 and n = 10, the expected output is 1024.00000.
If x = 2.10000 and n = 3, the expected output is 9.26100.
If x = 2.00000 and n = -2, the expected output is 0.25000, since 2^-2 = 1/2² = 1/4 = 0.25.

Consider the following constraints:

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n is an integer.
Either x is not zero or n > 0.
-10⁴ <= xⁿ <= 10⁴

Discuss:

What are the edge cases to consider (e.g., n = 0, n < 0)?
What is the time and space complexity of your solution?
Can you optimize the solution for better performance (e.g., using a divide-and-conquer approach)?

Provide code implementation for the solution.

Pow(x, n)

Medium

Google

2 views

Topics:

RecursionBit Manipulation

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ). This function should handle both positive and negative values of n.

For example:

If x = 2.00000 and n = 10, the expected output is 1024.00000.
If x = 2.10000 and n = 3, the expected output is 9.26100.
If x = 2.00000 and n = -2, the expected output is 0.25000, since 2^-2 = 1/2² = 1/4 = 0.25.

Consider the following constraints:

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n is an integer.
Either x is not zero or n > 0.
-10⁴ <= xⁿ <= 10⁴

Discuss:

What are the edge cases to consider (e.g., n = 0, n < 0)?
What is the time and space complexity of your solution?
Can you optimize the solution for better performance (e.g., using a divide-and-conquer approach)?

Provide code implementation for the solution.

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 are the possible ranges for x and n? Specifically, what is the range of the double x, and the range of the integer n?
Can n be negative? If so, how should I handle negative exponents?
Can x be zero? If so, what should I return if n is positive, negative, or zero?
Are you concerned about potential overflow issues with very large values of x or n?
Do you require a specific level of precision in the result, considering the use of doubles and potential for floating point errors?

Brute Force Solution

Approach

We need to calculate x raised to the power of n. The brute force way means directly multiplying x by itself n times. This is like repeatedly adding something to itself a specific number of times.

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

Start with a result equal to 1.
If n is positive, multiply the result by x, n times.
If n is zero, the result is 1 (because anything to the power of zero is one).
If n is negative, invert x by dividing one by x, then multiply the result by the inverted x, n times (making sure n is positive for the loop).
Return the final result.

Code Implementation

def power(base, exponent):
    result = 1

    if exponent > 0:
        for _ in range(exponent):
            result *= base

    elif exponent == 0:
        # Anything to the power of 0 is 1
        return 1

    else:
        # Handle negative exponents by inverting the base
        inverted_base = 1 / base

        for _ in range(abs(exponent)):
            result *= inverted_base

    return result

Big(O) Analysis

Time Complexity

O(n) – The described solution iteratively multiplies 'x' (or its inverse if 'n' is negative) by a running 'result' 'n' times when 'n' is not zero. The number of multiplications performed is directly proportional to the absolute value of the exponent 'n'. Therefore, the dominant operation is the loop that iterates up to 'n' times. This results in a linear time complexity with respect to the exponent 'n', making it O(n).

Space Complexity

O(1) – The provided algorithm calculates x to the power of n by iteratively multiplying x (or its inverse) and updating a result variable. This approach only requires a single variable to store the result and possibly a variable to track the loop counter (representing the number of times the multiplication happens). No auxiliary data structures that scale with the input size n are used. Therefore, the auxiliary space complexity is constant, independent of the input n.

Optimal Solution

Approach

Instead of repeatedly multiplying a number by itself, which can take a long time especially for large exponents, we use a 'divide and conquer' strategy. We break down the exponent into smaller parts, calculate the powers for those parts, and then combine them efficiently to get the final result. This clever approach dramatically reduces the number of calculations needed.

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

First, handle the simple cases: if the exponent is zero, the answer is always one. If the exponent is one, the answer is just the base number itself.
Now, consider the exponent. If it's negative, take the inverse of the base number and make the exponent positive. This turns our problem into calculating a positive power.
The clever part: think about repeatedly squaring the base. For example, x to the power of 4 is the same as (x squared) squared. This helps us reduce the number of multiplication steps.
Consider the exponent as a sum of powers of two. For example, x to the power of 5 is x to the power of (4 + 1), which is (x to the power of 4) times (x to the power of 1). So we can compute x to the power of 4 by squaring x twice, and then multiply that by x to get x to the power of 5.
Keep track of the result as we go. If the current part of the exponent is odd, multiply the current result by the current power of the base. Square the base in each step to get the next power.
By repeatedly squaring the base and multiplying into the result when needed based on the binary representation of the exponent, we can reach the desired power with far fewer calculations than multiplying the base by itself repeatedly.

Code Implementation

def power(base, exponent):
    if exponent == 0:
        return 1.0

    if exponent == 1:
        return base

    # Handle negative exponents by inverting the base.
    if exponent < 0:
        base = 1 / base
        exponent = -exponent

    result = 1.0
    current_power_of_base = base

    # Iterate through the bits of the exponent.
    while exponent > 0:
        # If the current bit is 1, multiply the result.
        if exponent % 2 == 1:
            result *= current_power_of_base

        # Square the base for the next power of 2.
        current_power_of_base *= current_power_of_base
        exponent //= 2

    return result

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a divide and conquer approach by repeatedly squaring the base and halving the exponent. The number of iterations is determined by how many times the exponent n can be divided by 2 until it reaches 0. This halving process is logarithmic. Therefore, the time complexity is proportional to the logarithm base 2 of n, which is O(log n).

Space Complexity

O(1) – The algorithm described calculates powers by repeatedly squaring the base and multiplying into a result. It uses a constant number of variables to store the base, exponent, result, and temporary calculations during the squaring and multiplication steps. The space used does not scale with the exponent, n, as there are no auxiliary data structures created that depend on the input size. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
n = 0	Any number to the power of 0 is 1, so return 1.0.
x = 0 and n < 0	Division by zero error will occur, so throw an exception or return a predefined error value (e.g., Infinity, NaN).
n = Integer.MIN_VALUE	Negating Integer.MIN_VALUE will cause integer overflow, so handle by converting n to a long and then negating.
x = 1	1 to any power is 1, so return 1.0.
x = -1 and n is odd	The result will be -1, so return -1.0.
x = -1 and n is even	The result will be 1, so return 1.0.
n is negative	Calculate x to the power of absolute value of n, then return 1 divided by the result.
Floating point precision issues with large n	Ensure algorithm is efficient (logarithmic time) to avoid excessive multiplication and thus reduce floating-point errors accumulation.

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 are the possible ranges for x and n? Specifically, what is the range of the double x, and the range of the integer n?
Can n be negative? If so, how should I handle negative exponents?
Can x be zero? If so, what should I return if n is positive, negative, or zero?
Are you concerned about potential overflow issues with very large values of x or n?
Do you require a specific level of precision in the result, considering the use of doubles and potential for floating point errors?

Brute Force Solution

Approach

We need to calculate x raised to the power of n. The brute force way means directly multiplying x by itself n times. This is like repeatedly adding something to itself a specific number of times.

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

Start with a result equal to 1.
If n is positive, multiply the result by x, n times.
If n is zero, the result is 1 (because anything to the power of zero is one).
If n is negative, invert x by dividing one by x, then multiply the result by the inverted x, n times (making sure n is positive for the loop).
Return the final result.

Code Implementation

def power(base, exponent):
    result = 1

    if exponent > 0:
        for _ in range(exponent):
            result *= base

    elif exponent == 0:
        # Anything to the power of 0 is 1
        return 1

    else:
        # Handle negative exponents by inverting the base
        inverted_base = 1 / base

        for _ in range(abs(exponent)):
            result *= inverted_base

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle the simple cases: if the exponent is zero, the answer is always one. If the exponent is one, the answer is just the base number itself.
Now, consider the exponent. If it's negative, take the inverse of the base number and make the exponent positive. This turns our problem into calculating a positive power.
The clever part: think about repeatedly squaring the base. For example, x to the power of 4 is the same as (x squared) squared. This helps us reduce the number of multiplication steps.
Consider the exponent as a sum of powers of two. For example, x to the power of 5 is x to the power of (4 + 1), which is (x to the power of 4) times (x to the power of 1). So we can compute x to the power of 4 by squaring x twice, and then multiply that by x to get x to the power of 5.
Keep track of the result as we go. If the current part of the exponent is odd, multiply the current result by the current power of the base. Square the base in each step to get the next power.
By repeatedly squaring the base and multiplying into the result when needed based on the binary representation of the exponent, we can reach the desired power with far fewer calculations than multiplying the base by itself repeatedly.

Code Implementation

def power(base, exponent):
    if exponent == 0:
        return 1.0

    if exponent == 1:
        return base

    # Handle negative exponents by inverting the base.
    if exponent < 0:
        base = 1 / base
        exponent = -exponent

    result = 1.0
    current_power_of_base = base

    # Iterate through the bits of the exponent.
    while exponent > 0:
        # If the current bit is 1, multiply the result.
        if exponent % 2 == 1:
            result *= current_power_of_base

        # Square the base for the next power of 2.
        current_power_of_base *= current_power_of_base
        exponent //= 2

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Any number to the power of 0 is 1, so return 1.0.
x = 0 and n < 0	Division by zero error will occur, so throw an exception or return a predefined error value (e.g., Infinity, NaN).
n = Integer.MIN_VALUE	Negating Integer.MIN_VALUE will cause integer overflow, so handle by converting n to a long and then negating.
x = 1	1 to any power is 1, so return 1.0.
x = -1 and n is odd	The result will be -1, so return -1.0.
x = -1 and n is even	The result will be 1, so return 1.0.
n is negative	Calculate x to the power of absolute value of n, then return 1 divided by the result.
Floating point precision issues with large n	Ensure algorithm is efficient (logarithmic time) to avoid excessive multiplication and thus reduce floating-point errors accumulation.