Skip to content

50. Pow(x, n)

Description

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

 

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
  • n is an integer.
  • Either x is not zero or n > 0.
  • -104 <= xn <= 104

Solutions

Solution 1: Mathematics (Fast Powering)

Thinking

The first idea is multiply \(x\) by itself \(|n|\) times. \(|n|\) reaches \(2^{31}\), so a linear loop times out; negative \(n\) also needs a reciprocal.

The bottleneck is multiplying by one \(x\) at a time. \(x^{2k} = (x^k)^2\) and \(x^{2k+1} = x \cdot (x^k)^2\) — the exponent halves each step.

Walk the bits of \(n\): square the base, and when a bit is \(1\) multiply into the answer. For negative \(n\), compute the positive power then take the reciprocal. Fast powering drops \(O(|n|)\) to \(O(\log |n|)\).

The core idea of the fast powering algorithm is to decompose the exponent \(n\) into the sum of \(1\)s on several binary bits, and then transform the \(n\)th power of \(x\) into the product of several powers of \(x\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\). Here, \(n\) is the exponent.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def qpow(a: float, n: int) -> float:
            ans = 1
            while n:
                if n & 1:
                    ans *= a
                a *= a
                n >>= 1
            return ans

        return qpow(x, n) if n >= 0 else 1 / qpow(x, -n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long) n);
    }

    private double qpow(double a, long n) {
        double ans = 1;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans = ans * a;
            }
            a = a * a;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    double myPow(double x, int n) {
        auto qpow = [](double a, long long n) {
            double ans = 1;
            for (; n; n >>= 1) {
                if (n & 1) {
                    ans *= a;
                }
                a *= a;
            }
            return ans;
        };
        return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long) n);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func myPow(x float64, n int) float64 {
    qpow := func(a float64, n int) float64 {
        ans := 1.0
        for ; n > 0; n >>= 1 {
            if n&1 == 1 {
                ans *= a
            }
            a *= a
        }
        return ans
    }
    if n >= 0 {
        return qpow(x, n)
    }
    return 1 / qpow(x, -n)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function myPow(x: number, n: number): number {
    const qpow = (a: number, n: number): number => {
        let ans = 1;
        for (; n; n >>>= 1) {
            if (n & 1) {
                ans *= a;
            }
            a *= a;
        }
        return ans;
    };
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
    #[allow(dead_code)]
    pub fn my_pow(x: f64, n: i32) -> f64 {
        let mut x = x;
        let n = n as i64;
        if n >= 0 {
            Self::quick_pow(&mut x, n)
        } else {
            1.0 / Self::quick_pow(&mut x, -n)
        }
    }

    #[allow(dead_code)]
    fn quick_pow(x: &mut f64, mut n: i64) -> f64 {
        // `n` should greater or equal to zero
        let mut ret = 1.0;
        while n != 0 {
            if (n & 0x1) == 1 {
                ret *= *x;
            }
            *x *= *x;
            n >>= 1;
        }
        ret
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
    const qpow = (a, n) => {
        let ans = 1;
        for (; n; n >>>= 1) {
            if (n & 1) {
                ans *= a;
            }
            a *= a;
        }
        return ans;
    };
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public double MyPow(double x, int n) {
        return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long)n);
    }

    private double qpow(double a, long n) {
        double ans = 1;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans *= a;
            }
            a *= a;
        }
        return ans;
    }
}

Comments