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 Sam K., 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.

More Goldman Sachs coding interview questions

See all Goldman Sachs problems →