Fast Exponentiation
Mediumxⁿ via repeated squaring · O(log n)
To compute a power fast, square the result of half the power instead of multiplying one at a time.
The idea
Instead of multiplying x by itself n times, square the base and halve the exponent: xⁿ = (x²)^(n/2) for even n, or x·xⁿ⁻¹ for odd n. This gives O(log n) multiplications.
10
5
2
1
0
0
1
2
3
4
Step 1 of 11. pow(2, 10): halve the exponent each call — O(log n) multiplications. Values: 10, 5, 2, 1, 0.
1/11
Optimal
timeO(log n)spaceO(log n)
Halve the exponent each step.
1function pow(x, n) {2 if (n === 0) return 1;3 const half = pow(x, Math.floor(n / 2));4 return n % 2 ? x * half * half : half * half;5}Input
- array
- [10, 5, 2, 1, 0]
Memory
- exp
- —
Output
- value
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- x = 2, n = 10
- Output:
- 1024
- Explanation:
- 2^10 = 1024.
Example 2
- Input:
- x = 2, n = -2
- Output:
- 0.25
- Explanation:
- Negative power → 1/4 = 0.25.
Example 3
- Input:
- x = 3, n = 0
- Output:
- 1
- Explanation:
- Anything to the 0 is 1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.