Leetcode 50 - Pow(x,n)

Note:

  • Using normal iteration by multiplying x every time will cause TLE.
  • 2^32 = (2^16)^2 = ((2^8)^2)^2 = (((2^4)^2)^2)^2 = ((((2^2)^2)^2)^2)^2.
  • Instead of multiplying x, do (x^2)^(n/2) every time.
  • It’s called exponentiation by squaring.
  • Leave one x out when n is odd.

Question:

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

Example:

1
2
Input: x = 2.00000, n = 10
Output: 1024.00000

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
if (n === 0) return 1;
if (n < 0) return myPow(1/x, -n);
if (n & 1 === 1) {
return x*myPow(x, n-1);
} else {
return myPow(x, n/2)**2;
}
};