Skip to main content

50. Pow(x, n)

mediumAsked at Goldman Sachs

Compute x raised to the power n in O(log n). Goldman Sachs uses Pow(x, n) to test 'fast exponentiation' — the moment you say 'I'll square x repeatedly and use the binary representation of n' is the moment they decide to advance you.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs Strats and SWE reports include Pow(x, n) as a fast-exponentiation question with the negative-n edge case.
  • LeetCode Discuss (2025-12)— Pow(x, n) appears in the top-20 of LeetCode's Goldman Sachs company tag.

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.

Approaches

1. Linear multiplication

Multiply x by itself |n| times, then invert if n < 0.

Time
O(n)
Space
O(1)
function myPowLinear(x, n) {
  if (n === 0) return 1;
  const N = n < 0 ? -n : n;
  let result = 1;
  for (let i = 0; i < N; i++) result *= x;
  return n < 0 ? 1 / result : result;
}

Tradeoff: Times out for |n| > 10^7 — at INT_MAX you'd never finish. Mention briefly then move to fast exponentiation.

2. Fast exponentiation by squaring (optimal)

x^n = (x*x)^(n/2) for even n, and x * x^(n-1) for odd n. Cuts the work to O(log n).

Time
O(log n)
Space
O(1)
function myPow(x, n) {
  let N = n;
  if (N < 0) { x = 1 / x; N = -N; }
  let result = 1;
  while (N > 0) {
    if (N % 2 === 1) result *= x;
    x *= x;
    N = Math.floor(N / 2);
  }
  return result;
}

Tradeoff: O(log n) iterations. The iterative version above avoids recursion-stack overflow on INT_MIN. The 'flip sign and invert x once' at the top handles negatives cleanly.

3. Recursive divide-and-conquer

Same idea, expressed recursively: pow(x, n) = pow(x*x, n/2) for even n.

Time
O(log n)
Space
O(log n)
function myPowRec(x, n) {
  if (n === 0) return 1;
  if (n < 0) return 1 / myPowRec(x, -n);
  if (n % 2 === 0) return myPowRec(x * x, n / 2);
  return x * myPowRec(x * x, (n - 1) / 2);
}

Tradeoff: Cleaner to write but uses O(log n) stack. Watch the INT_MIN case — -INT_MIN overflows in 32-bit langs. The iterative version is safer for Goldman's Java/C++ rounds.

Goldman Sachs-specific tips

Goldman Sachs interviewers want to hear 'exponentiation by squaring' or 'fast power' by name before you start coding. The negative-n edge case is a Goldman favorite — be ready to handle n = -2147483648 (the INT_MIN trap where you can't simply negate). The iterative version is the safer answer; recursion is fine in JS but flagged in Java/C++ rounds.

Common mistakes

  • Recursing on n = INT_MIN where -n overflows.
  • Forgetting the n = 0 case (any x^0 is 1).
  • Mixing up '<<' or '/2' for unsigned types vs signed — Goldman's Java round will catch this.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Modular exponentiation: x^n mod m for cryptography. (Same template, mod everywhere.)
  • Matrix exponentiation — apply the same trick to A^n where A is a matrix.
  • What if n is a floating-point number? (log + exp, but then sqrt cases need rationals.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does INT_MIN need special handling?

Because |INT_MIN| > INT_MAX in two's complement. If you naively flip the sign of n = -2147483648, you get an overflow in Java/C++ — the value 'fits' nowhere. Solutions: use a 64-bit accumulator for the absolute value, or invert x once upfront so the absolute-value math is on a positive number that always fits.

Why is the answer O(log n) and not O(log |x^n|)?

Because the number of multiplications is determined by the bit-length of |n|, not the size of the result. The result's magnitude is bounded by the problem statement (|x^n| <= 10^4), so you never need extra-precision arithmetic in this specific problem.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Pow(x, n) and other Goldman Sachs interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →