Pow(x, n) medium

Problem Statement

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

Example 1

  • Input: x = 2.00000, n = 10
  • Output: 1024.00000

Example 2

  • Input: x = 2.10000, n = 3
  • Output: 9.26100

Steps and Explanation

The naive approach is to simply multiply x by itself n times. However, this has a time complexity of O(n), which is inefficient for large values of n. A more efficient approach uses recursion and the concept of exponentiation by squaring.

Exponentiation by Squaring: This technique leverages the following property:

xn = (xn/2)2 if n is even xn = x * (x(n-1)/2)2 if n is odd

By recursively breaking down the problem into smaller subproblems using this property, we significantly reduce the number of multiplications required. We handle negative exponents by taking the reciprocal of the positive exponent's result.

Algorithm:

  1. Handle base cases: If n is 0, return 1 (x0 = 1). If n is negative, negate n and store the result to be used for the reciprocal at the end.
  2. Recursive calculation:
    • If n is even, recursively calculate pow(x, n/2) and square the result.
    • If n is odd, recursively calculate pow(x, (n-1)/2), square the result, and multiply by x.
  3. Handle negative exponent: If the original n was negative, return 1 divided by the calculated result.

Code (C#)

public class Solution {
    public double MyPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            x = 1 / x;
            n = -n; // Handle negative exponents
        }

        return helper(x, n);
    }

    private double helper(double x, int n) {
        if (n == 0) return 1;
        if (n % 2 == 0) {
            double halfPow = helper(x, n / 2);
            return halfPow * halfPow;
        } else {
            double halfPow = helper(x, (n - 1) / 2);
            return x * halfPow * halfPow;
        }
    }
}

Complexity Analysis

  • Time Complexity: O(log n). The recursive calls reduce the problem size by half in each step, leading to logarithmic time complexity.
  • Space Complexity: O(log n). This is due to the recursive call stack. In the worst case, the depth of the recursion is proportional to the logarithm of n. This can be improved to O(1) using an iterative approach, though the recursive version is often considered more readable.