Skip to main content

50. Pow(x, n)

medium

Compute x raised to the integer power n in O(log n) time using fast exponentiation. The textbook divide-and-conquer problem — with a subtle edge case at INT_MIN.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31 - 1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -10^4 <= x^n <= 10^4

Examples

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^2 = 1/4 = 0.25.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive O(n) multiplication times out for n near 2^31.

Hint 2

Fast exponentiation: x^n = (x^(n/2))^2 if n is even; x * x^(n-1) if odd. Drops to O(log n).

Hint 3

Iterative version: walk the bits of n. Maintain a running base = x. For each set bit, multiply the result by base; then square base.

Hint 4

Handle negative n: compute x^|n| and return 1 / that. But beware — |INT_MIN| overflows 32-bit. Cast n to a wider type or handle the edge case explicitly.

Solution approach

Reveal approach

Fast exponentiation by squaring. Convert n to a wide-enough type (long/int64) to handle |INT_MIN|. If n < 0, set x = 1/x and n = -n. Initialize result = 1, base = x. While n > 0: if n is odd, multiply result *= base. Square base *= base. Right-shift n. Return result. The bit-walking gives O(log n) multiplications, each O(1). Total O(log n) time, O(1) space. Recursive variant: pow(x, n) = pow(x*x, n/2) if n even; x * pow(x, n-1) if n odd; base case pow(x, 0) = 1. Watch the negative-n / INT_MIN trap — that's the bug interviewers look for.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • divide-and-conquer
  • math
  • binary-exponentiation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg
  • LinkedIn

More Math practice problems

See all Math problems →