Compute a Power Using Fast Exponentiation
Solve this Problemx and a non-negative integer exponent n, compute x raised to the power n.
Multiplying x by itself n times works, but it treats every exponent as fundamentally n separate units of work. Recursive squaring exploits a shortcut instead: x^n is just (x^(n/2))² when n is even (with one extra factor of x tacked on when n is odd) — so the exponent can be halved at every single recursive call rather than merely decremented. Reaching the base case (n=0, trivially 1) this way takes only O(log n) calls, turning what would be a million multiplications for a million-sized exponent into roughly twenty.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
-10 ≤ x ≤ 10, x ≠ 0 - ◆
0 ≤ n ≤ 20 - ◆
The result always fits comfortably within a 32-bit signed integer for this input range
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Multiply x by Itself n Times
BruteStart a running product at 1 and multiply it by x, n times in a row. Completely correct, but the amount of work grows linearly with the exponent — doubling n doubles the number of multiplications needed, even though the final answer only grows exponentially larger, not exponentially more expensive to reach.
O(n)O(1)1class Solution {
2 public int computePower(int x, int n) {
3 long result = 1;
4 for (int i = 0; i < n; i++) {
5 result *= x;
6 }
7 return (int) result;
8 }
9}Optimal — Recursive Squaring
Optimalx^n can be built from a much smaller piece: x^(n/2), squared — since x^n = (x^(n/2))² whenever n is even. If n is odd, one extra factor of x is needed after squaring. Recursing this way halves the exponent at every single call, so reaching the base case (n=0, where the answer is trivially 1) takes only O(log n) calls — computing 2²⁰ this way takes roughly 20 multiplications' worth of recursive calls, not 2²⁰ of them.
O(log n)O(log n) call-stack space1class Solution {
2 public int computePower(int x, int n) {
3 return (int) fastPow(x, n);
4 }
5
6 private long fastPow(int x, int n) {
7 if (n == 0) return 1;
8 long half = fastPow(x, n / 2);
9 long result = half * half;
10 if (n % 2 == 1) result *= x;
11 return result;
12 }
13}