Algorithms to Compute the Math Power(a, n) in logarithm Complexi

  • 时间：2020-10-11 15:17:18
  • 分类：网络文摘
  • 阅读：151 次

Implement pow(x, n), which calculates x raised to the power n (xn). Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

Bruteforce Algorithms to Compute the Math Power(a, n)

The most straightforward solution is to iteratively multiple the answer n times of a i.e. a^n. This requires O(N) time and O(1) space.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        for i in range(n):
            res *= x
        return res        
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        for i in range(n):
            res *= x
        return res

Please note that we have turned the negative power a^(-n) to 1.0/(a^n). Given n is a large number e.g. 2^(31), this algorithm will time out.

Algorithms to Compute the Math Power(a, n) in logarithm Complexity using Divide and Conquer

The optimal solution is to apply the divide and conquer technique. If we want to compute a^n, we can divide this into two cases. When n is odd, the answer is a^(n-1)*a, and when n is even, the answer is (a^(n//2))^2.

This algorithm gives us the O(logN) time. You can implement this algorithm using Recursion:

1
2
3
4
5
6
7
8
9
10

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

Alternatively, the iterated approach works just fine (more code, but saving the cost of Recursive calls, removing the stack overflows):

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

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

C++ Implementation of Computing the Power(a, n)

Iterative approach and handling the negative cases quite well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    double pow(double x, int n) {
        //  check the sign of n
        bool plus = n >= 0;
        n = plus ? n : -n;
        double r = 1;
        while (n > 0) {
            // if odd
            if (n & 1 == 1) {
                r *= x;
            }
            // reduce the exponential to its half
            n /= 2;
            // square the base
            x *= x;
        }
        // if n < 0, should return 1.0/x^n
        return plus ? r : 1.0 / r;
    }
};
class Solution {
public:
    double pow(double x, int n) {
        //  check the sign of n
        bool plus = n >= 0;
        n = plus ? n : -n;
        double r = 1;
        while (n > 0) {
            // if odd
            if (n & 1 == 1) {
                r *= x;
            }
            // reduce the exponential to its half
            n /= 2;
            // square the base
            x *= x;
        }
        // if n < 0, should return 1.0/x^n
        return plus ? r : 1.0 / r;
    }
};

Same iterative approach, however handle the negative cases via calling itself recursively. Also, please note that we negative n, which means that we have to handle the overflow manually or giving it a larger int64_t type. i.e. negate -2147483648 will cause integer overflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        double res = 1;
        while (n > 1) {
            if (n % 2 == 0) {
                x = x * x;
                n /= 2;
            } else {
                res = res * x;
                n --;
            }
        }
        return res * x;
    }
};
class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        double res = 1;
        while (n > 1) {
            if (n % 2 == 0) {
                x = x * x;
                n /= 2;
            } else {
                res = res * x;
                n --;
            }
        }
        return res * x;
    }
};

Last but not least, recursive implementation in C++ (shorter/concise code with Recursion):

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

class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        if (n % 2 == 0) {
            double a = myPow(x, n / 2);
            return a * a;
        } 
        return x * myPow(x, n - 1);
    }
};
class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        if (n % 2 == 0) {
            double a = myPow(x, n / 2);
            return a * a;
        } 
        return x * myPow(x, n - 1);
    }
};

Have you got a better solution/implementation to compute the Math Power(a, n)? Leave comments below to share!

--EOF (The Ultimate Computing & Technology Blog) --

推荐阅读：
最少要付多少元的租金　 此时水的高度是多少　 将原有水果卖出40%后　 求这五个整数的平均数　 求AB两地距离及原计划行驶时间　 运输队要运2000件玻璃器皿　 5厘米宽的纸6等分　 据称是难倒数学教授的小学奥数题　 3个动物进行200米的赛跑　 8个谜语全猜对的有多少人　
评论列表
添加评论