Problem description:

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

1
2
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

1
2
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

1
2
3
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

  • 100.0 < x < 100.0
  • 231 <= n <= 2311
  • 104 <= xn <= 104

Solution:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/504874ea-b97c-4c54-abe7-cf9889488b98/Untitled.png

Iterative example

1
2
3
4
5
6
7
8
9
10
11
12
2^15

				power current_product
init   		1					2
15%2
15//2			2					2^2							
7%2
7//2			2^3				2^4							
3%2
3//2			2^7				2^8
1%2
1//2			2^15			2^16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # check if n is negative
        if n < 0:
            x = 1/x
            n = -n
        # We solve the positive power here:
        power = 1
        current_product = x
        while n > 0:
            # if n is odd number, we need to time x one more time
            if n%2 : 
                power = power * current_product
            current_product = current_product * current_product
            n = n//2
        return power

Recursive 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def myPow(self, x: float, n: int) -> float:

        def function(base = x, exponent = abs(n)):
            if exponent == 0:
                return 1
            elif exponent % 2 == 0:
                return function(base * base, exponent // 2)
            else:
                return base * function(base * base, (exponent - 1) // 2)

        f = function()
        
        return float(f) if n >= 0 else 1/f

time complexity: $O()$
space complexity: $O()$
reference:
related problem: