algoadvance

Implement the function double myPow(double x, int n) that calculates x raised to the power n (i.e., x^n). Be careful of overflow for large values of n.

Clarifying Questions

1. Q: Can n be negative? A: Yes, n can be negative, and in such cases, we need to return (1 / x^{-n}).

2. Q: What is the range for x and n? A: x is a double, and n is a 32-bit signed integer.

3. Q: How should we handle edge cases, like ( x = 0 ) or ( n = 0 )? A: Any number raised to 0 is 1. (0^0 \text{ is traditionally considered to be 1}).

Strategy

1. Base Cases:
   • If ( n == 0 ): Return 1 (since any number raised to the power 0 is 1).
   • If ( n < 0 ): Compute the positive power and take the reciprocal.
2. Recursive or Iterative Approach:
   • For efficient calculation, use the method of Exponentiation by Squaring.
   • This reduces the time complexity significantly by breaking the count into halves recursively or iteratively.

Code

Let’s write the code using an iterative approach with Exponentiation by Squaring for better efficiency.

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    current_product = x

    while n > 0:
        if n % 2 == 1:
            result *= current_product
        current_product *= current_product
        n //= 2

    return result

Time Complexity

• Time Complexity: O(log n), because we are reducing the power by half at each step due to the divide-by-2 operation.
• Space Complexity: O(1), because we are not using recursive calls, thus no extra space on the call stack.

This approach ensures that the function efficiently handles large values of n, including negative powers.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?