Pow(x, n)

Pow(x, n)

What is this problem about?

The Pow(x, n) problem implements fast exponentiation — computing x^n efficiently. The key insight is that exponentiation can be done in O(log n) by repeatedly squaring (fast exponentiation / binary exponentiation). This Pow(x, n) coding problem is a fundamental algorithm with widespread applications. The math and recursion interview pattern is the core.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because fast exponentiation is foundational for cryptography, hashing, and number theory. It tests both recursive and iterative divide-and-conquer thinking.

Algorithmic pattern used

Binary exponentiation (fast power). Recursively: pow(x, n) = pow(x, n//2) * pow(x, n//2) if n is even, or x * pow(x, n//2) * pow(x, n//2) if n is odd. Handle negative n: pow(1/x, -n). Iterative: while n > 0, if n is odd multiply result by x, then x = x*x, n = n//2.

Example explanation

pow(2, 10):

• pow(2,5) = 2 * pow(2,2) * pow(2,2) = 2 * 4 * 4 = 32.
• pow(2,10) = pow(2,5)^2 = 32^2 = 1024.

pow(2,-3) = 1/pow(2,3) = 1/8 = 0.125.

Common mistakes candidates make

• Not handling negative exponents (must invert x and negate n).
• Integer overflow when n is INT_MIN (n = -n overflows for 32-bit int).
• Recursive depth O(log n) — acceptable; iterative avoids stack overhead.
• Not squaring x each step in iterative approach.

Interview preparation tip

Binary exponentiation is a must-know algorithm. Memorize both recursive and iterative implementations. The critical edge cases: n=0 (return 1), n<0 (return 1/pow(x,-n)), x=0 (return 0 for n>0). The iterative version processes bits of n from LSB to MSB, multiplying result when the bit is 1. Practice modular exponentiation (pow(x, n, mod)) as the extended version used in cryptography and number theory.