Pow(x, n)

MediumMathfast exponentiation

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Implement a function that computes x raised to the power n (that is, x^n), where x is a floating-point number and n is an integer. The exponent n may be positive, negative, or zero. A negative exponent means you raise x to the corresponding positive power and then take the reciprocal of the result. The straightforward approach of multiplying x by itself n times runs in O(n) time, which is too slow when n is very large (up to roughly two billion in magnitude). Your goal is to do better by exploiting the structure of exponentiation. The key observation is that x^n can be broken down by repeated squaring: x^n = (x^(n/2))^2 when n is even, and x^n = x * (x^((n-1)/2))^2 when n is odd. By halving the exponent at each step, you can compute the result in O(log n) multiplications. This technique is known as fast (or binary) exponentiation. Return the computed value as a double.

Examples

Input: x = 2.0, n = 10
Output: 1024.0
2.0 raised to the 10th power equals 1024.0.
Input: x = 2.1, n = 3
Output: 9.261
2.1 * 2.1 * 2.1 = 9.261.
Input: x = 2.0, n = -2
Output: 0.25
A negative exponent gives the reciprocal: 2.0^(-2) = 1 / (2.0^2) = 1 / 4 = 0.25.

Constraints

  • `-100.0 < x < 100.0`
  • `-2^31 <= n <= 2^31 - 1`
  • `n` is an integer.
  • Either `x` is not zero or `n` is greater than zero.
  • The final result is guaranteed to fit within the range of a double-precision float (`-10^4 <= x^n <= 10^4`).

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.