Jonas Notes

Pow(x,n)

2 min read

Problem

Pow(x,n)

Approach

The first kickoff question to ask yourself is why does x ** n not work? A quick try, and we will realise that it actually does. But that’s not the point of the question isn’t it. Let’s take a deeper look into how exponentiation is done.

In other languages like C++ and Java, we have to import a library to do the exponentiation for us. This makes this question much more meaningful in those languages. So how can exponentiation be done?

Approach 1: The naive way We can just have a for loop that loops n times, and continuously get the product sum, as seen here.

for _ in range(n): res *= x

But that would be O(n) time, could we do better than that? As seen from the leetcode constraints, the n can be very large

Approach 2: Fast Exponentiation This is what the question wants us to implement. The whole idea of the exponentiation is for us to do it in log(n) time. When n is even, x ** n = (x ** n/2) ** 2 and when n is odd, x ** n = x * (x ** n-1) Since multiplication is O(1) (tripped up there, multiplication is done by hardware, and can be represented as one assembly instruction, MUL), we can achieve exponentiation in O(logn) time.

I originally coded the odd case exactly what I wrote above.

else: return x * self.myPow(x, n-1)

but experienced an overflow. We can actually just divide it first, since its a floor, then multiply as seen below.

Complexity

  • Time: O(logn)
  • Space: O(1)

Code

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        if n < 0: return 1 / self.myPow(x, abs(n))
        if n == 0: return 1.0
        if n == 1: return x
        half = self.myPow(x, n//2)
        if n % 2 == 0: return half * half
        else: return half * half * x

Backlinks