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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Pow(x, n) and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →