algoadvance

Leetcode 50. Pow(x, n)

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (x^n).

Clarifying Questions

  1. Can x be any real number?
    • Yes.
  2. Can n be any integer, including negative values?
    • Yes.
  3. What are the constraints on the input values x and n?
    • Typically, constraints on such problems are within the range of double precision for x and within the range of int for n.
  4. Are there any special cases we need to handle?
    • Yes, we need to handle cases like when n is 0 (return 1), or when x is 0 (consider edge cases with n being positive, negative or zero).

Strategy

We can solve this problem using an efficient algorithm known as Exponentiation by Squaring, which works in O(log n) time complexity. This method helps in reducing the time complexity compared to a naive approach which would take O(n) time.

Approach:

  1. Handle Edge Cases:
    • If x is 0:
      • If n is positive, return 0.
      • If n is zero, typically 0 raised to the power 0 is considered as 1.
      • If n is negative, handle by returning a statement (It’s generally undefined; mathematically referred to as infinity).
    • If n is 0, return 1 since any number raised to the power 0 is 1.
  2. Handling Negative Power:
    • If n is negative, compute the positive power of 1/x to the absolute value of n.
  3. Exponentiation by Squaring:
    • Recursively break down the power into smaller components.
    • If n is even, x^n can be broken down into (x * x)^(n / 2).
    • If n is odd, x^n can be broken down into x * x^(n - 1).

Code

#include <iostream>
#include <cmath>

class Solution {
public:
    double myPow(double x, int n) {
        // Edge cases:
        if (x == 0) {
            if (n > 0) return 0;
            else if (n == 0) return 1;
            else return INFINITY; // undefined case for x = 0 and n < 0
        }
        if (n == 0) return 1;
        if (n == 1) return x;
        
        long long N = n; // To handle INT_MIN case
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        
        return fastPow(x, N);
    }
    
private:
    double fastPow(double x, long long n) {
        if (n == 0) return 1.0;
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
};

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

Time Complexity

The time complexity of the above solution is O(log n):

The space complexity is O(log n) due to the recursive call stack for the fastPow function.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI