Pow(x, n) Explained

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Handle both positive and negative exponents, and ensure the result is a double. This problem tests your ability to optimize exponentiation using techniques like binary exponentiation.

Example

Input: x = 2.00000, n = 10

Output: 1024.00000

Explanation: 2^10 = 1024.

Code

public class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double result = 1, current = x;
        while (N > 0) {
            if ((N % 2) == 1) result *= current;
            current *= current;
            N /= 2;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.myPow(2.0, 10)); // 1024.0
    }
}
            

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    result = 1
    current = x
    while n > 0:
        if n % 2 == 1:
            result *= current
        current *= current
        n //= 2
    return result

# Example usage
print(my_pow(2.0, 10))  # 1024.0
            

function myPow(x, n) {
    let N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    let result = 1, current = x;
    while (N > 0) {
        if (N % 2 === 1) result *= current;
        current *= current;
        N = Math.floor(N / 2);
    }
    return result;
}

// Example usage
console.log(myPow(2.0, 10)); // 1024.0
            

Explanation

• If n is negative, invert x and make n positive.
• Use binary exponentiation: process n’s binary representation.
• For each bit, square the current value; if the bit is 1, multiply the result by the current value.
• Divide n by 2 each iteration.
• Return the final result.

Note