Calculate the Power of a Number
Solve this ProblemEasy10 min
Topics
BasicsLoopsRecursionMath
Companies
TCSInfosysWipro
Given an integer
base and a non-negative integer exponent, return base raised to the power of exponent (base^exponent).
The loopMultiplication LoopStarting result at 1 and multiplying it by base exactly exponent times. version is the direct reading of what a power means — repeated multiplication. The fast exponentiationFast ExponentiationSplitting the exponent in half at each step (squaring the result) instead of subtracting 1 — base^exponent = (base^(exponent/2))² when exponent is even. version — also called binary exponentiation — exploits the fact that base^exponent can be built from a problem roughly HALF its size instead of just one smaller, cutting the work from exponent steps down to about log₂(exponent).
Test Case 1:
Input:base = 2, exponent = 10
Output:1024
Explanation:2 multiplied by itself 10 times.
Test Case 2:
Input:base = 5, exponent = 0
Output:1
Explanation:Any number to the power of 0 is 1.
Test Case 3:
Input:base = -3, exponent = 3
Output:-27
Explanation:A negative base with an odd exponent stays negative.
Constraints
- ◆
-100 ≤ base ≤ 100 - ◆
0 ≤ exponent ≤ 20
Try the Dry Run
Approach & Solutions
Loop — Multiply exponent TimesGood
Start a running result at 1, and multiply it by base, exactly exponent times. exponent = 0 needs no multiplications at all — the loop simply never runs, leaving result at 1.
Time
O(exponent)Space
O(1)Java
1class Solution {
2 public long calculatePower(int base, int exponent) {
3 long result = 1;
4 for (int i = 0; i < exponent; i++) {
5 result = result * base;
6 }
7 return result;
8 }
9}Fast Exponentiation — Divide the Exponent in HalfOptimal
base^exponent can be built from a problem half the size: if exponent is even, base^exponent = (base^(exponent/2))². If it's odd, pull out one extra factor of base first: base^exponent = base × base^(exponent-1), where exponent-1 is now even. Each step roughly halves the exponent instead of subtracting 1 from it, so the whole computation finishes in about log₂(exponent) multiplications instead of exponent of them.
Time
O(log exponent)Space
O(log exponent) call-stack spaceJava
1class Solution {
2 public long calculatePower(int base, int exponent) {
3 if (exponent == 0) {
4 return 1;
5 }
6 if (exponent % 2 == 0) {
7 long half = calculatePower(base, exponent / 2);
8 return half * half;
9 }
10 return base * calculatePower(base, exponent - 1);
11 }
12}