DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Pow(x, n)

mediumRecursion

Problem statement

Write a function that raises a floating-point number x to an integer power n, without calling the language's built-in power function or operator. The exponent can be zero or negative, and it can be as large in magnitude as a 32-bit signed integer allows, including -2^31.

A negative exponent means the reciprocal: x^-n = 1 / x^n.

Examples

Example 1

Input: x = 3.0, n = 4

Output: 81.00000

Example 2

Input: x = 2.0, n = -3

Output: 0.12500

Explanation: 2^-3 = 1 / 2^3 = 1 / 8.

Hints

Approach

Use exponentiation by squaring. Look at the exponent in binary: x^13 = x^8 · x^4 · x^1 because 13 = 1101 in binary. Keep squaring a base (x, x^2, x^4, x^8, ...) and multiply it into the result whenever the matching bit of the exponent is set.

  1. Convert the exponent to a long m. If it is negative, set x = 1 / x and m = -m.
  2. While m > 0: if m is odd, result *= x. Then x *= x and m //= 2.
  3. Return result.

The loop runs once per bit of the exponent, so at most 32 times for a 32-bit input. The long conversion matters in Java: negating Integer.MIN_VALUE as an int gives back Integer.MIN_VALUE.

ComplexityTime O(log |n|)Space O(1)
Python
class Solution:
def myPow(self, x: float, n: int) -> float:
m = n
if m < 0:
x, m = 1 / x, -m
result = 1.0
while m:
if m & 1: # this bit of the exponent is set
result *= x
x *= x # x, x^2, x^4, x^8, ...
m >>= 1
return result

Follow-up questions

  • Compute x^n mod m for large integers without overflow.
  • Implement exponential backoff where the delay is base * 2^attempt, capped at a maximum, without overflowing.

Frequently asked questions

-n overflows: the positive value 2147483648 does not fit in an int, so negating Integer.MIN_VALUE returns the same negative number and the loop never runs correctly. Copy n into a long before negating it.

Yes: pow(x, m) = pow(x, m / 2)^2, times an extra x when m is odd. It is the same O(log n) idea with O(log n) stack depth. The iterative loop avoids the stack and is just as short.

Repeated squaring shows up wherever powers or modular powers are needed quickly, including the modular exponentiation inside RSA and Diffie-Hellman key exchange that TLS relies on. More commonly, it is a check that you handle overflow and sign edge cases carefully, which matters when you compute things like exponential backoff delays.