Pow(x,n)
EasySquare and multiply, driven by the bits
Problem
Compute x^n efficiently using binary (fast) exponentiation.
Square as you halve the exponent (fast power): x^10 = (x^5)^2, so far fewer multiplications.
The idea
Read the exponent's bits from the bottom: square the base each step and multiply it into the result whenever the current bit is set. That is O(log n) multiplications instead of n.
The trick
- `while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }`.
- Negative n: invert the base and negate the exponent, minding INT_MIN.
- The same loop under a modulus is modular exponentiation.
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.