Pow(x, n)
EasySquare the half power
Problem
Compute x raised to the power n (n may be negative) using fast exponentiation.
Square as you halve the exponent (fast power) — far fewer multiplications.
The idea
x^n is (x^(n/2))² for even n, and x times that for odd n. Halving the exponent each step makes it O(log n) instead of multiplying n times.
The trick
- Compute the half power once and square it — calling twice reverts to O(n).
- Negative n: compute the positive power and take the reciprocal.
- Watch the most negative integer when negating n.
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.