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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pow(x, n)

Number: 50

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Bloomberg, LinkedIn, Microsoft, Citadel, Walmart Labs, Oracle, ServiceNow, Goldman Sachs, Salesforce, Apple, Adobe, TikTok, Uber, Yahoo, J.P. Morgan, tcs, Accenture, Millennium, EPAM Systems, Wix

Problem Description

Implement a function to calculate x raised to the power n (i.e., x^n). This function must handle both positive and negative exponents, while ensuring an efficient solution even for large values of n.

Key Insights

  • Use exponentiation by squaring to reduce the number of multiplications.
  • For a negative exponent, compute the power for |n| and then take the reciprocal.
  • Handle the edge case when n is 0 (return 1).
  • The algorithm works in O(log n) time complexity.

Space and Time Complexity

Time Complexity: O(log |n|)
Space Complexity: O(1) for the iterative solution, or O(log |n|) if implemented recursively

Solution

We use exponentiation by squaring, an algorithm that reduces the number of multiplications by repeatedly squaring the base and halving the exponent. Here's how it works:

  1. If n is negative, switch x to 1/x and n to -n.
  2. Initialize the result as 1.
  3. Loop while n is greater than 0:
    • If the current n is odd, multiply the result by x.
    • Square the base x.
    • Divide n by 2 (using integer division). This iterative approach efficiently computes the power in logarithmic steps. The same approach can be implemented recursively.

Code Solutions

# Python implementation of pow(x, n) using exponentiation by squaring
def myPow(x, n):
    # if exponent is negative, invert x and make n positive
    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0  # initialize result
    while n:
        # if the current exponent is odd, multiply result by the base
        if n % 2:
            result *= x
        x *= x  # square the base for the next iteration
        n //= 2  # divide the exponent by 2
    return result

# Example usage:
print(myPow(2.0, 10))  # Output: 1024.0
print(myPow(2.1, 3))   # Output: 9.261000000000001
print(myPow(2.0, -2))  # Output: 0.25
← Back to All Questions