Pow(x, n)
Asked at Oracle, Walmart
Problem
Implement pow(x, n) which calculates x raised to the power n. The fast exponentiation approach reduces time from O(n) to O(log n) by squaring.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Naive: multiply x by itself n times. O(n). Too slow for large n.
Fast exponentiation: x^n = (x^(n/2))^2 if n is even, x * x^(n-1) if n is odd. This halves the problem each step → O(log n).
Why it works: x^8 = (x^4)^2 = ((x^2)^2)^2. You only need 3 squarings instead of 7 multiplications.
Handle negative n: x^(-n) = 1 / x^n. Convert n to positive and flip the result.
Visual walkthrough for pow(2, 10):
10 is even: pow(2,10) = pow(2,5)^2
5 is odd: pow(2,5) = 2 * pow(2,4)
4 is even: pow(2,4) = pow(2,2)^2
2 is even: pow(2,2) = pow(2,1)^2
1 is odd: pow(2,1) = 2 * pow(2,0)
pow(2,0) = 1
Unwind: pow(2,1)=2, pow(2,2)=4, pow(2,4)=16, pow(2,5)=32, pow(2,10)=1024.
Edge cases: n=0 (return 1), n=1 (return x), x=0, n=INT_MIN (special case to avoid overflow when negating).
Optimal Approach
Recursive:
Step 1: Base case — if n == 0, return 1.
Step 2: If n is odd: result = x * pow(x, n-1).
Step 3: If n is even: result = pow(x, n/2) ^ 2.
Step 4: If n < 0: x = 1/x, n = -n.
Iterative (bit manipulation):
- If n is negative, flip x to 1/x and n to -n.
- For each bit in n: if bit is 1, multiply result by current x. Square x at each step.
Time: O(log n) — n is halved at each step. Space: O(log n) recursive, O(1) iterative.
What Trips People Up in Real Interviews
Using the naive O(n) loop. The interviewer expects O(log n) fast exponentiation. Squaring at each step halves the exponent.
Not handling negative exponents. If n < 0, compute 1 / pow(x, -n). Flip the sign and invert the base.
Integer overflow when negating INT_MIN. n = -INT_MIN overflows in 32-bit. Use long or handle the edge case separately.
Forgetting that x^0 = 1 for any x (including 0). The base case must return 1 when n == 0.
Using recursion without memoization. The recursive approach is O(log n) because each call halves n. No memoization needed.
Solution Code
def myPow(x, n):
if n == 0:
return 1.0
if n < 0:
x = 1 / x
n = -n
result = 1.0
while n > 0:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return resultFrequently Asked Questions
What is the Pow(x, n) problem?
Implement `pow(x, n)` which calculates x raised to the power n. The `fast exponentiation` approach reduces time from `O(n)` to `O(log n)` by squaring.
How do you solve Pow(x, n)?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Pow(x, n)?
Pow(x, n) is asked at Oracle, Walmart. It is a medium difficulty problem.
What are common mistakes on Pow(x, n)?
- Using the naive `O(n)` loop. The interviewer expects `O(log n)` fast exponentiation. Squaring at each step halves the exponent.
- Not handling negative exponents. If n < 0, compute `1 / pow(x, -n)`. Flip the sign and invert the base.
- Integer overflow when negating INT_MIN. `n = -INT_MIN` overflows in 32-bit. Use `long` or handle the edge case separately.
- Forgetting that `x^0 = 1` for any x (including 0). The base case must return 1 when n == 0.
- Using recursion without memoization. The recursive approach is `O(log n)` because each call halves n. No memoization needed.