Problem
Implement pow(x, n) which calculates x raised to the power n. Must run faster than naive O(n).
Example
Input: x = 2.0, n = 10
Output: 1024.0Solution
Fast exponentiation. x^n = (x^(n/2))^2 if n is even, else x * x^(n-1). Handle negative n by taking 1/result.
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
result = 1
while n:
if n & 1:
result *= x
x *= x
n >>= 1
return resultfunction myPow(x, n) {
if (n < 0) { x = 1 / x; n = -n; }
let result = 1;
while (n) {
if (n & 1) result *= x;
x *= x;
n = Math.floor(n / 2);
}
return result;
}double myPow(double x, int n) {
long N = n;
if (N < 0) { x = 1 / x; N = -N; }
double result = 1;
while (N) {
if (N & 1) result *= x;
x *= x;
N >>= 1;
}
return result;
}public double myPow(double x, int n) {
long N = n;
if (N < 0) { x = 1 / x; N = -N; }
double result = 1;
while (N > 0) {
if ((N & 1) == 1) result *= x;
x *= x;
N >>= 1;
}
return result;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
Each iteration squares x and halves n. Bit by bit of n decides whether to multiply result by current x. Use long for n to handle INT_MIN negation.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?