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

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

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) --

推荐阅读：
How to Mirror a Binary Tree?　 中文视听网手机版中文视听APP(最新版)下载　 作文写作指导：小学生作文该怎么写？　 小学作文需增长孩子的视野，鼓励孩子表达　 六年级劳动节作文　 五年级作文：不该丢失的童年色彩　 六年级作文：我和秋天有个约会　 数学故事：流传久远的算术趣题　 趣味数学：什么是完全数　 数学小故事：高斯巧解算术题　
评论列表
添加评论