Pow(x, n) medium

Problem Statement

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

Steps and Explanation

The naive approach of repeatedly multiplying x, n times, has a time complexity of O(n), which is inefficient for large values of n. A more efficient approach uses recursion and binary exponentiation.

Binary Exponentiation: This technique leverages the fact that:

• xⁿ = (x^n/2)² if n is even
• xⁿ = x * (x^(n-1)/2)² if n is odd

By recursively breaking down the problem using these rules, we can significantly reduce the number of multiplications required. The time complexity becomes O(log n).

We also need to handle negative exponents and the edge case where n is 0. For negative exponents, we calculate the reciprocal of x^|n|. For n = 0, the result is always 1.

Code (C++)

#include <iostream>
#include <cmath>

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1; // Handle base case: x^0 = 1
        if (n < 0) return 1.0 / myPow(x, -n); // Handle negative exponents

        double result = myPowHelper(x, n);
        return result;
    }

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


int main(){
    Solution sol;
    std::cout << sol.myPow(2.00000, 10) << std::endl; // Output: 1024
    std::cout << sol.myPow(2.10000, 3) << std::endl;  // Output: 9.261
    std::cout << sol.myPow(2.00000, -2) << std::endl; // Output: 0.25
    return 0;
}

Complexity Analysis

• Time Complexity: O(log n) due to the binary exponentiation algorithm. The number of recursive calls is proportional to the number of bits in the binary representation of n.
• Space Complexity: O(log n) in the worst case due to the recursive call stack. This space complexity can be improved to O(1) by using an iterative approach instead of recursion. However, the recursive solution is generally easier to understand.