50. Pow(x, n).md

50. Pow(x, n)

1. Description

Implement pow(x, n), which calculates $x$ raised to the power $n$ (i.e. $x^{n}$).

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/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

Solution 1: Language: C Exponentiation by Squaring

Wikipedia contributors. (2020, October 21). Exponentiation by squaring. In Wikipedia, The Free Encyclopedia. Retrieved 17:53, October 22, 2020, from https://en.wikipedia.org/w/index.php?title=Exponentiation_by_squaring&oldid=984687029

Pure mathematics solution by reducing the power recursively. The method is based on the observation that, for a positive integer $n$, we have

$$ x^n = \begin{cases} x , ( x^{2})^{\frac{n - 1}{2}}, & \text{if } n \text{ is odd} \\ (x^{2})^{\frac{n}{2}} , & \text{if } n \text{ is even.} \end{cases} $$

Note that the $O(n)$ complexity solution would exceed the time limit.

• Friday, 23 October, 2020
• Time Complexity: $O(\log{}{n})$
• Space Complexity: $O(\log{}{n})$
• Runtime: 0 ms, faster than 100.00% of C online submissions for Pow(x, n).
• Memory Usage: 5.6 MB, less than 38.51% of C online submissions for Pow(x, n).

// The last bit of x in binary must be 1 if x is an odd number, so `x & 1` is
// `1`. Additionally, if x is an even number the bit operating should get a `0`.
double myPow(double x, long long n) {
    if (n < 0) {
        return myPow(1 / x, -n);
    } else if (n == 0.0) {
        return 1.0;
    } else if (n == 1.0) {
        return x;
    // if x is odd:
    } else if (n & 1) {
        return x * myPow(x * x, (n - 1) / 2);
    // if x is even:
    } else {
        return myPow(x * x, n / 2);
    }
}