Fast Power
Problem
Raise a number to an integer exponent without multiplying it by itself that many times. The exponent may be zero or negative, and a negative exponent means one divided by the positive-exponent result. Return the value.
Examples
Input: base = 2, exp = 10
Output: 1024
Why: ten multiplications are not needed; four calls sufficeInput: base = 2, exp = -3
Output: 0.125
Why: a negative exponent inverts the positive resultInput: base = 3, exp = 0
Output: 1
Why: edge case, any base to the zero is oneHints
0 / 3
Multiplying the base exp times is the obvious loop. Ask what an even exponent lets you say about half of it.
The result for exp is built from the result for exp // 2, and that sub-result is needed twice — but only has to be computed once.
Recurse on exp // 2, square what comes back, and multiply by the base once more when the exponent is odd. Handle exponent zero as the base case and flip a negative exponent at the top.
Solution
Squaring halves the exponent, so each call cuts the work in two rather than shaving one off. The key detail is storing the recursive result in a variable and squaring it: calling twice would rebuild the same subtree and collapse the saving back to linear. An odd exponent leaves one base factor behind after the halving, which the last multiplication puts back. Negative exponents are handled once at the top by inverting the positive answer. Time is O(log exp) and the stack depth is the same.
def power(base, exp):
if exp == 0:
return 1 # anything to the zero
if exp < 0:
return 1 / power(base, -exp) # a negative exponent flips it
half = power(base, exp // 2) # one call, reused twice
return half * half * (base if exp % 2 else 1)
print(power(2, 10)) # -> 1024
print(power(3, 0)) # -> 1
print(power(2, -3)) # -> 0.125Stuck on the idea rather than the code? Factorial and Fibonacci covers it.