Jobs

Interviews

Discussions

Pow(x, n)

Medium

Pow(x, n)

Medium

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? Can x be zero? Can n be negative?
If x is 0 and n is negative, what should I return? Should I throw an exception or return a specific value?
What level of precision is expected in the result? Is there a tolerance for rounding errors considering we are working with floating-point numbers?
Is 'n' guaranteed to be an integer, or should I handle the case where 'n' is a floating point number?
Are there any performance expectations or constraints I should be aware of, considering the potential range of 'n'?

Brute Force Solution

Approach

The basic idea is to repeatedly multiply the base number by itself. If the exponent is positive, we just multiply the base that many times. If the exponent is negative, we'll deal with that case separately, because it is equivalent to one divided by the base raised to the positive exponent.

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

First, consider the case where the exponent is zero. In that case, the result is always one.
If the exponent is positive, start with the base number.
Multiply the base number by itself, and keep doing this repeatedly. Each time, reduce the exponent value by one, tracking the number of multiplications.
Continue this process until the exponent reaches zero.
The final result is the accumulated product after all these multiplications.
If the exponent is negative, calculate the base raised to the positive absolute value of the exponent using the above procedure.
Then, take one and divide it by the result obtained in the previous step. This gives the correct answer for a negative exponent.

Code Implementation

def power_function_brute_force(base, exponent):
    if exponent == 0:
        return 1

    if exponent > 0:
        result = base

        # Repeatedly multiply the base by itself
        exponent_tracker = exponent - 1

        while exponent_tracker > 0:
            result *= base
            exponent_tracker -= 1

        return result

    # Account for negative exponent by taking reciprocal
    else:
        positive_exponent = abs(exponent)
        result = base

        # Repeatedly multiply the base by itself
        exponent_tracker = positive_exponent - 1

        while exponent_tracker > 0:
            result *= base
            exponent_tracker -= 1

        # Invert result for negative powers
        return 1 / result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates a number of times equal to the absolute value of the exponent n. When n is positive, there is a single loop that multiplies the base by itself n times. When n is negative, the absolute value of n is taken, and then there is a single loop that multiplies the base by itself abs(n) times. Therefore, the number of operations grows linearly with the input n, and the time complexity is O(n).

Space Complexity

O(1) – The plain English explanation outlines an iterative process involving multiplication and decrementing the exponent. It only requires storing a few variables like the base, the exponent (which is decremented), and the accumulated product. No auxiliary data structures such as lists, arrays, or hash maps are used. The memory needed for these variables remains constant irrespective of the size of the exponent (n), therefore the auxiliary space complexity is O(1).

Optimal Solution

Approach

Calculating a number to a large power by multiplying it repeatedly is slow. A faster way involves repeatedly squaring the base and adjusting the exponent, effectively reducing the number of multiplication operations required.

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 original number.
If the exponent is negative, take the inverse of the base and make the exponent positive. We will eventually compute this positive power, so dealing with the negative now will simplify calculations later.
Now, repeatedly square the base and halve the exponent. If the exponent is odd at any point, multiply the current result by the current base. By halving, we mean integer division, discarding any remainder.
Continue squaring the base and halving the exponent until the exponent reaches zero. At that point, the accumulated result is the answer.

Code Implementation

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

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

    result = 1

    # Repeatedly square the base and halve the exponent.
    while exponent > 0:
        # If the exponent is odd, multiply the result by the base.
        if exponent % 2 == 1:
            result *= base

        base *= base

        # Integer division to halve the exponent.
        exponent //= 2

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The dominant operation in this algorithm is repeatedly halving the exponent n in each iteration of the loop. Each division by 2 brings the exponent closer to zero. The number of times the exponent can be halved before reaching zero is logarithmic with respect to the initial value of n. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores a few variables to keep track of the base, exponent, and the intermediate result. The space required by these variables does not depend on the size of the exponent (n) or the base (x). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
x is 0 and n is negative	Return positive infinity (or throw an exception depending on language) as division by zero is undefined.
x is 0 and n is 0	Return 1 as 0^0 is generally considered 1.
n is Integer.MIN_VALUE (most negative integer)	Handle potential overflow when negating n by first converting x to its inverse if x!=1 and x!=-1 and then processing it correctly, or consider long.
x is 1	Return 1 immediately as 1 raised to any power is 1.
x is -1 and n is even	Return 1.
x is -1 and n is odd	Return -1.
n is 0	Return 1 as any number raised to the power of 0 is 1.
Large x and n leading to potential floating point overflow	Be aware of the limits of floating point representation and the potential for overflow, and potentially suggest using logarithms and exponentiation if extremely large numbers are expected.

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? Can x be zero? Can n be negative?
If x is 0 and n is negative, what should I return? Should I throw an exception or return a specific value?
What level of precision is expected in the result? Is there a tolerance for rounding errors considering we are working with floating-point numbers?
Is 'n' guaranteed to be an integer, or should I handle the case where 'n' is a floating point number?
Are there any performance expectations or constraints I should be aware of, considering the potential range of 'n'?

Brute Force Solution

Approach

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

First, consider the case where the exponent is zero. In that case, the result is always one.
If the exponent is positive, start with the base number.
Multiply the base number by itself, and keep doing this repeatedly. Each time, reduce the exponent value by one, tracking the number of multiplications.
Continue this process until the exponent reaches zero.
The final result is the accumulated product after all these multiplications.
If the exponent is negative, calculate the base raised to the positive absolute value of the exponent using the above procedure.
Then, take one and divide it by the result obtained in the previous step. This gives the correct answer for a negative exponent.

Code Implementation

def power_function_brute_force(base, exponent):
    if exponent == 0:
        return 1

    if exponent > 0:
        result = base

        # Repeatedly multiply the base by itself
        exponent_tracker = exponent - 1

        while exponent_tracker > 0:
            result *= base
            exponent_tracker -= 1

        return result

    # Account for negative exponent by taking reciprocal
    else:
        positive_exponent = abs(exponent)
        result = base

        # Repeatedly multiply the base by itself
        exponent_tracker = positive_exponent - 1

        while exponent_tracker > 0:
            result *= base
            exponent_tracker -= 1

        # Invert result for negative powers
        return 1 / result

Try it yourself on LeetCode

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 original number.
If the exponent is negative, take the inverse of the base and make the exponent positive. We will eventually compute this positive power, so dealing with the negative now will simplify calculations later.
Now, repeatedly square the base and halve the exponent. If the exponent is odd at any point, multiply the current result by the current base. By halving, we mean integer division, discarding any remainder.
Continue squaring the base and halving the exponent until the exponent reaches zero. At that point, the accumulated result is the answer.

Code Implementation

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

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

    result = 1

    # Repeatedly square the base and halve the exponent.
    while exponent > 0:
        # If the exponent is odd, multiply the result by the base.
        if exponent % 2 == 1:
            result *= base

        base *= base

        # Integer division to halve the exponent.
        exponent //= 2

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
x is 0 and n is negative	Return positive infinity (or throw an exception depending on language) as division by zero is undefined.
x is 0 and n is 0	Return 1 as 0^0 is generally considered 1.
n is Integer.MIN_VALUE (most negative integer)	Handle potential overflow when negating n by first converting x to its inverse if x!=1 and x!=-1 and then processing it correctly, or consider long.
x is 1	Return 1 immediately as 1 raised to any power is 1.
x is -1 and n is even	Return 1.
x is -1 and n is odd	Return -1.
n is 0	Return 1 as any number raised to the power of 0 is 1.
Large x and n leading to potential floating point overflow	Be aware of the limits of floating point representation and the potential for overflow, and potentially suggest using logarithms and exponentiation if extremely large numbers are expected.