Topic describes

Implement POw (x, n), that is, calculate x to the NTH power function (i.e., xn). Library functions should not be used and large numbers should not be considered. Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000

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

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

Hint: -100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104

1. The dichotomy O(log2n)

X to the NTH, we can view it as x to the n over 2 times x to the n over 2, and then we can use the dichotomy, again we use a map for pruning

Example code 1:

def myPow(x: float, n: int) - >float:
    def helper(x, n) :
        if n == 0:
            return 1

        if n in visit:
            return visit[n]

        if n & 1= =0:  X ^ (n//2) * x ^ (n//2)
            res = helper(x, n // 2) * helper(x, n // 2)
            visit[n] = res
            return res
        else: If n is even, divide and conquer by x * x ^ (n//2) * x ^ (n//2)
            res = x * helper(x, n // 2) * helper(x, n // 2)
            visit[n] = res
            return res

    # Add a map to record the calculated value for pruning
    visit = {}

    if n > 0:
        return helper(x, n) If n is positive or negative
    else:
        return 1 / helper(x, -n)
Copy the code

2. Fast power O(n)

Example code 2:

def myPow(x: float, n: int) - >float:
    if x == 0:
        return 0
    if n < 0:
        x, n = 1 / x, -n If n is less than 0, convert the data
    res = 1
    while n > 0:
        if n & 1= =1:
            res *= x If the current bit is 1, multiply the weights
        x *= x # Weight accumulation
        n >>= 1 # Shift n to the left for the next loop
    return res
Copy the code

Again, the fast power method is much more efficient than the dichotomy method