Pow(x, n)

Write a function that raises a floating-point number x to an integer power n and returns xn.

The exponent can be positive, zero or negative, and it can be as large as about two billion in absolute value, so multiplying x by itself n times is far too slow. A negative exponent means the reciprocal: x-n = 1 / xn. Any x raised to the power 0 is 1.

Do not call a built-in power function or operator. Answers within 10^-5 of the exact value (relative error for large results) are accepted.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Math, Bits & Strings · problem 40 of 169

Start simple

Multiply x into the result |n| times: O(|n|) time, about two billion multiplications in the worst case.

The key idea

The key identity is x2k = (xk)2: one squaring doubles the exponent. That is called fast exponentiation or exponentiation by squaring.

Write n in binary, say 13 = 1101₂ = 8 + 4 + 1. Then x13 = x8 · x4 · x1. Keep a variable base that takes the values x, x2, x4, x8, … by squaring it each round, and multiply it into the result exactly when the matching bit of n is 1. Shift n right each round; when it reaches 0 you are done.

There are only as many rounds as n has bits, at most 31 here, so the running time is O(log |n|).

For a negative exponent, compute the power of 1/x with exponent -n. In languages with 32-bit integers, -n overflows when n = -231, so store the exponent in a 64-bit variable before negating.

Complexity

• Time: O(log |n|)
• Space: O(1)

Python

class Solution:
    def myPow(self, x, n):
        if n < 0:                 # x^(-n) == (1/x)^n
            x, n = 1 / x, -n
        result = 1.0
        base = x                  # takes the values x, x^2, x^4, x^8, ...
        while n > 0:
            if n & 1:             # this bit of n is set: include this power
                result *= base
            base *= base
            n >>= 1
        return result

JavaScript

var myPow = function(x, n) {
  if (n < 0) {               // x^(-n) == (1/x)^n
    x = 1 / x;
    n = -n;
  }
  let result = 1;
  let base = x;              // takes the values x, x^2, x^4, x^8, ...
  while (n > 0) {
    if (n % 2 === 1) result *= base;   // this bit of n is set
    base *= base;
    n = Math.floor(n / 2);   // n can be 2^31, too big for 32-bit bit operators
  }
  return result;
};

What the interviewer is checking

It checks that you know divide-and-conquer exponentiation and handle the edge cases (negative and minimum-integer exponents) without being prompted.

Mistakes to avoid

• Negating n = -2³¹ in a 32-bit int, which overflows back to a negative number.
• A linear loop over n, which times out for exponents in the billions.
• The recursive version computing pow(x, n/2) twice per call, which is O(n) again instead of O(log n).
• Forgetting that n = 0 must return 1 even for negative x.

Follow-ups to expect

• How would you compute (a^b) mod m for huge b? (Same loop, reduce mod m.)
• Can you raise a matrix to a power fast? (Same squaring idea, matrix multiply.)
• How do precision errors grow here? (One rounding per multiplication, about 2·log n.)

In real software

Modular exponentiation in RSA and Diffie-Hellman, and matrix powers for fast Fibonacci or graph path counts, all use repeated squaring.

Practice next