Scale Engineer

Pow(x, n)

Med
#0050Time: O(n)Space: O(1)26 companies
Patterns
MathRecursion
Companies
AccentureAdobeAmazonApple

Prompt

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

 

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/22 = 1/4 = 0.25

 

Constraints:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -104 <= xn <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

The algorithm handles three main cases for the exponent n:

  1. Positive n: We initialize a result to 1.0 and multiply it by x exactly n times in a loop.
  2. n is zero: By definition, x^0 is 1, so we return 1.0.
  3. 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

Time

O(n)

Space

O(1)

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem