0050 - Pow(x, n) (Medium)

Problem Link

https://leetcode.com/problems/powx-n/

Problem Statement

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
• -2^31 <= n <= 2^31 - 1
• -10^4 <= x^n <= 10^4

Approach 1: Binary Exponentiation

If the exponent $n$ is negative, we need to change it to positive exponent $- n$ and make the base to $1 / x$. Then apply Binary Exponentiation.

Time Complexity: $O(log n)$ instead of calculating $x * x$, $n$ times. We can utilize binary exponentiation to reduce the number of calculations to $log n$ time.

Space Complexity: $O(1)$, we can perform it iteratively, with constant extra space.

C++

Written by @wingkwong

class Solution {
public:
    double myPow(double x, int N) {
        long long n = N;
        if (n < 0) n = -n, x = 1 / x;
        // Binary Exponentiation
        double ans = 1;
        if (n == 0) return 1;
        while (n > 0) {
            if(n & 1) ans *= x;
            x *= x;
            n >>= 1;
        }
        return ans;
    }
};

Python

Written by @ColeB2

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # negative n --> adjust our starting x and n. So the exponent
        # is positive, and the x value is 1/x
        if (n < 0):
            n = -n 
            x = 1 / x
        # initialize our running answer, num, as 1.
        num = 1
        # while we have an exponent:
        while n > 0:
            # if exponent is odd ie: n % 2 == 1:
            if n & 1:
                # multiply answer by current x value.
                num *= x
            # multiply x value, by itself.
            x *= x
            # integer division --> n = n // 2
            n >>= 1
        return num