Pow(x, n)

MEDIUM

Description

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

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n is an integer.
Either x is not zero or n > 0.
-10⁴ <= xⁿ <= 10⁴

Approaches

Checkout 3 different approaches to solve Pow(x, n). Click on different approaches to view the approach and algorithm in detail.

Brute Force using Simple Loop

This approach simulates the basic definition of exponentiation by repeatedly multiplying the base x for n times. It's the most straightforward but least efficient method.

Algorithm

Convert the integer n to a long N to handle the Integer.MIN_VALUE case.
If N is negative, update x to 1/x and N to -N.
Initialize a variable ans to 1.0.
Iterate from 0 to N-1.
In each iteration, multiply ans by x.
After the loop, return ans.

The algorithm handles three main cases for the exponent n:

Positive n: We initialize a result to 1.0 and multiply it by x exactly n times in a loop.
n is zero: By definition, x^0 is 1, so we return 1.0.
Negative n: We use the property x^-n = 1 / x^n. To avoid integer overflow when n is Integer.MIN_VALUE, we first convert n to a long. Then, we can safely negate it. We calculate the power for the positive exponent -n and then take its reciprocal. A small optimization for the negative case is to compute (1/x)^-n instead.

public class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double ans = 1.0;
        for (long i = 0; i < N; i++) {
            ans = ans * x;
        }
        return ans;
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Very simple to understand and implement.
Works correctly for small values of n.

Cons:

Extremely inefficient for large values of n.
Will result in a 'Time Limit Exceeded' (TLE) error on most online judges due to the O(n) complexity.

Code Solutions

Checking out 5 solutions in different languages for Pow(x, n). Click on different languages to view the code.

public class Solution {
    public double MyPow(double x, int n) {
        return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long) n);
    }
    private double qpow(double a, long n) {
        double ans = 1;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans *= a;
            }
            a *= a;
        }
        return ans;
    }
}

Video Solution

Watch the video walkthrough for Pow(x, n)

Patterns:

MathRecursion

Companies:

Accenture |Adobe |Amazon |Apple |