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

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.

• 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;
}
}

• 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);
}
};

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


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

• 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);
}


• /**
* @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);
};


• 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;
}
}

• impl Solution {
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)
}
}

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