Leetcode: Power (x, n)

Pow(x, n) | LeetCode OJ

The brute force way is to multiply x, n times. This will lead to n computations. We can use divide and conquer approach to solve this.

1. For an even n find x^(n/2) and multiply it with itself
2. For an odd n find x^((n-1)/2) multiply it with itself and then multiply by x

The above process is recursive, we can do the same using iteration

1. Start with single x
2. If the remaining power is even we square the current number and reduce the remaining power to half
3. if remaining power is odd we multiply x and reduce it by 1
4. Continue the process till remaining power is 1 and finally multiply an x

For eg. suppose x=2 and n=9

res, n = ²⁰, 9 → odd n → res, n = ²¹, 8

res, n = ²¹, 8 → even n → res, n = ²², 4

res, n = ²², 8 → even n → res, n = ²⁴, 2

res, n =²⁴, 2 → even n → res, n = ²⁸, 1

Remarks:

1. O(log n) time complexity
2. O(1) space complexity

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        res = 1
        x = 1 / x if n < 0 else (1 if n == 0 else x)
        m = abs(n)
        while m > 1:
            if m % 2:
                res *= x
                m -= 1
            x = x * x
            m /= 2
        return res * x