Problem Statement in English

You’re given a float x and an integer n. You have to calculate x raised to the power n (i.e. $x^n$).

Approach

You could solve this problem by simply multiplying the base x with itself n times. But that would be very inefficient. Instead, we can use the method of binary exponentiation.

The idea is this: If we want to calculate $x^n$, we can break it down as follows:

  • If n is even, then $x^n = (x^{n/2})^2$
  • If n is odd, then $x^n = x * x^{n-1}$, and since n-1 is even, we can reduce it to the expression above, and solve it using that formula.

That’s pretty much it. Just rinse and repeat until we get to the base case, which is when n is 0, in which case we’re done.

Also make sure to account for negative exponents, in which case we can simply take the reciprocal of the base and make the exponent positive.

Solution in Python

class Solution:
    class Solution:
    def myPow(self, x: float, n: int) -> float:
        def rec(base, exponent):
            res = 1
            neg = exponent < 0
            if exponent < 0:
                exponent *= -1

            while exponent:
                if exponent % 2:
                    res *= base
                base *= base
                exponent //= 2

            return res if not neg else 1/res
        
        return rec(x, n)

Complexity

  • Time: $O(log n)$
    Where $n$ is the exponent. We are halving the exponent at every step.

  • Space: $O(1)$
    Since we’re using constant space.

Mistakes I Made

I had to look up this binary exponentiation method.

And we are done.