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

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

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

推荐阅读：
奥数题:小军骑车从家里出发到某地参观　 数学题:现在有牛，羊，马吃一块草地的草，草均匀的生长　 数学题:利用图中的阴影部分刚好可以做成一个圆柱形油桶　 数学题:水面高度正好是圆锥高度的一半　 数学题:把高是10cm的圆柱按下图切开，分成17份　 数学题：一批同学画画，2人合用一瓶红颜料　 数学题:再加多少毫升牛奶，才可以把杯子装满？　 把圆柱削成一个最大的圆锥求削去部分体积　 用一张半径为15厘米的半圆形纸片围成一个圆锥　 归期将近，珍惜相遇　
评论列表
添加评论