[tabby title=”Task”]

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

 

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/2

²

 = 1/4 = 0.25

 

Constraints:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• -10⁴ <= xⁿ <= 10⁴

This problem was taken from https://leetcode.com/problems/powx-n/

 

[tabby title=”Solution”]

 

Brute force solution:

Straight forward, but we have to consider negative ranges.

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    
    if(n === 0) {
        return 1;
    }

    var N = n;
    var X = x;
    var result = 1;
    
    if(n < 0) {
        X = 1 / x;
        N = -n;
    }
    
    for(var i = 0; i < N; i ++) {
        result = result * X;
    }  
    return result;
};

 

Approach 2: Fast Power Algorithm Recursive

• divide n so you immediately cut the computation time in half to logarithmic one.

 

 

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    
    function fastPow(x, n) {
        if(n < 1) {
            return 1;
        }
        var half = fastPow(x, Math.floor(n / 2));

        if(n % 2 == 0) {
            return half * half;
        }
        else {
            return half * half * x;
        }
    }
    
    var X = x;
    var N = n;
    if(n < 0) {
        X = 1 / x;
        N = -n;        
    }
    return fastPow(X, N);
    
};

 

 

[tabbyending]