DSA Tracker

Visualize

Pow(x, n)

Instead of multiplying x by itself n times (O(n)), halve the exponent each step: if n is even, x^n = (x^(n/2))^2; if odd, x^n = x * x^(n-1). This gets the answer in O(log n) multiplications. A negative n is handled by inverting x (1/x) and negating n first.

Details

Animated on: Fast exponentiation: x=2.0, n=10 (answer 1024.0). Halve n each step: n even → x=x*x,n/=2; n odd → result*=x,n-=1. Negative n inverts x first.

Problem:Pow(x, n)Medium

Math

step 1 / 12

10
[0]

Step 1: myPow(2.0, 10). n=10 ≥ 0, so no sign flip. Call fastPow(2.0, 10).

  • n=0· arr[0] = 10
Pseudocode
1FUNCTION myPow(x, n):
2  IF n < 0: replace x with 1/x and n with -n
3  RETURN fastPow(x, n)
4FUNCTION fastPow(x, n):
5  IF n is 0: RETURN 1
6  IF n is even:
7    half = fastPow(x, n/2)
8    RETURN half * half
9  ELSE:
10    RETURN x * fastPow(x, n-1)

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Step 1: myPow(2.0, 10). n=10 ≥ 0, so no sign flip. Call fastPow(2.0, 10).
  2. Step 2: fastPow(2.0, 10). n=10 is even. Compute half = fastPow(2.0, 10/2) = fastPow(2.0, 5), then square it. x stays 2.0, n becomes 5 for the recursive call.
  3. Step 3: fastPow(2.0, 5). n=5 is odd. Compute x * fastPow(x, n-1) = 2.0 * fastPow(2.0, 4). x stays 2.0, n becomes 4.
  4. Step 4: fastPow(2.0, 4). n=4 is even. Compute half = fastPow(2.0, 4/2) = fastPow(2.0, 2), then square it. x stays 2.0, n becomes 2.
  5. Step 5: fastPow(2.0, 2). n=2 is even. Compute half = fastPow(2.0, 2/2) = fastPow(2.0, 1), then square it. x stays 2.0, n becomes 1.
  6. Step 6: fastPow(2.0, 1). n=1 is odd. Compute x * fastPow(x, n-1) = 2.0 * fastPow(2.0, 0). x stays 2.0, n becomes 0.
  7. Step 7: fastPow(2.0, 0). n=0, base case. Return 1. This is the termination condition that starts the unwind.
  8. Step 8: Unwind. fastPow(2.0, 1) = x * 1 = 2.0 * 1 = 2.0. n=1 result is 2.
  9. Step 9: Unwind. fastPow(2.0, 2) = (fastPow(2.0, 1))^2 = 2.0^2 = 4.0. Square the previous result.
  10. Step 10: Unwind. fastPow(2.0, 4) = (fastPow(2.0, 2))^2 = 4.0^2 = 16.0. Square the n=2 result.
  11. Step 11: Unwind. fastPow(2.0, 5) = x * fastPow(2.0, 4) = 2.0 * 16.0 = 32.0. Multiply x by the n=4 result.
  12. Step 12: Unwind. fastPow(2.0, 10) = (fastPow(2.0, 5))^2 = 32.0^2 = 1024.0. Square the n=5 result. Final answer: 1024.0.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Pow(x, n) in the editorAll Math problemsBack to roadmap