Intermediate Level
Implement the powIntegerFast method that calculates an integer power efficiently using fast exponentiation.
The input contains two integers: base and exponent. Your task is to calculate base raised to the power exponent.
The exponent is treated as a non-negative integer. For example, 2|10 means 2 multiplied by itself 10 times, so the result is 1024.
Example 1
Input
base (int) =
2exponent (int) =
10Returns (int)
1024Example 2
Input
base (int) =
3exponent (int) =
3Returns (int)
27Example 3
Input
base (int) =
5exponent (int) =
0Returns (int)
1Use fast exponentiation instead of multiplying the base one time for every exponent value.
The idea is to repeatedly square the base and reduce the exponent by half. When the current exponent is odd, multiply the answer by the current base.
This reduces the number of operations from linear time to logarithmic time.
Pseudocode:
function powIntegerFast(base, exponent):
result = 1
while exponent > 0:
if exponent is odd:
result = result * base
base = base * base
exponent = exponent / 2
return resultReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run