Pow(x, n)

Pow(x, n)

What is this problem about?

The Pow(x, n) problem implements fast exponentiation — x raised to the power n — using binary exponentiation (exponentiation by squaring). This achieves O(log n) instead of naive O(n) multiplication. The math and recursion interview pattern is the core, and this appears in cryptography, competitive programming, and systems engineering.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because fast power is a fundamental algorithm. It tests divide-and-conquer thinking and understanding of how bit representation of n determines the multiplications needed. The key is recognizing that x^n = (x^(n/2))^2.

Algorithmic pattern used

Binary exponentiation. Recursive: if n=0 return 1; if n<0 return 1/pow(x,-n); if n is even return pow(x,n//2)^2; if n is odd return x * pow(x,n//2)^2. Iterative: maintain result=1; while n>0: if n is odd, result*=x; x*=x; n//=2.

Example explanation

pow(2, 13) (binary: 1101):

• n odd: result*=2, x=4, n=6.
• n even: x=16, n=3.
• n odd: result*=16=32, x=256, n=1.
• n odd: result*=256=8192=2^13. ✓

Common mistakes candidates make

• INT_MIN overflow: if n = Integer.MIN_VALUE, -n overflows in Java/C++. Use long.
• Not handling x=0 with n=0 edge case.
• Recursive approach without memoizing the half-power (computing it twice).
• Off-by-one in even/odd split.

Interview preparation tip

Pow(x, n) is the template for all "exponentiation in O(log n)" operations. Master both recursive and iterative. The iterative version processes bits of n from LSB to MSB — cleaner for avoiding integer overflow. Also know modular exponentiation pow(x, n, mod) for competitive programming and cryptography contexts. This directly extends to matrix exponentiation for O(log n) Fibonacci and linear recurrence computation.