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.
implSolution{#[allow(dead_code)]pubfnmy_pow(x:f64,n:i32)->f64{letmutx=x;letn=nasi64;ifn>=0{Self::quick_pow(&mutx,n)}else{1.0/Self::quick_pow(&mutx,-n)}}#[allow(dead_code)]fnquick_pow(x:&mutf64,mutn:i64)->f64{// `n` should greater or equal to zeroletmutret=1.0;whilen!=0{if(n&0x1)==1{ret*=*x;}*x*=*x;n>>=1;}ret}}
1 2 3 4 5 6 7 8 9101112131415161718
/** * @param {number} x * @param {number} n * @return {number} */varmyPow=function(x,n){constqpow=(a,n)=>{letans=1;for(;n;n>>>=1){if(n&1){ans*=a;}a*=a;}returnans;};returnn>=0?qpow(x,n):1/qpow(x,-n);};