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-1n 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 1s on several binary bits, and then transform the nth 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.
PythonJavaC++GoTypeScriptRustJavaScriptC#
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)(code-box)
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;
}
}(code-box)
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);
}
};(code-box)
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)
}(code-box)
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);
}(code-box)
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
}
}(code-box)
/**
* @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);
};(code-box)
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;
}
}(code-box)
