50. Pow(x, n)

Problem

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

Example 1:

Input: 2.00000, 10 Output: 1024.00000 

Example 2:

Input: 2.10000, 3 Output: 9.26100 

Example 3:

Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

Solution

/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function(x, n) { if (n === 0) return 1; if (n > 0) return pow(x, n); if (n < 0) return 1 / pow(x, -n); }; var pow = function (x, n) { if (n === 1) return x; var num = pow(x, Math.floor(n / 2)); if (n % 2 === 0) { return num * num; } else { return x * num * num; } }; 

Explain:

二分、递归。注意 n 小于 0 的情况。

Complexity:

• Time complexity : O(log(n)).
• Space complexity : O(log(n)).