We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Pow(x, n)

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires calculating a power, which can involve both positive and negative exponents.
  • A negative exponent indicates the reciprocal of the positive exponent (e.g., x^(-n) = 1/(x^n)).
  • The algorithm can use a method called exponentiation by squaring to reduce the time complexity.
  • The method takes advantage of the fact that:
    • x^n = (x^(n/2))^2 if n is even
    • x^n = x * x^(n-1) if n is odd

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution employs the exponentiation by squaring technique, which helps in efficiently calculating the power by reducing the number of multiplications needed. The algorithm works recursively or iteratively, depending on whether n is even or odd, and also handles negative exponents by calculating the reciprocal.

Code Solutions

def myPow(x: float, n: int) -> float:
    if n < 0:
        x = 1 / x
        n = -n
    result = 1
    while n:
        if n % 2:  # If n is odd
            result *= x
        x *= x  # Square the base
        n //= 2  # Divide n by 2
    return result
← Back to All Questions