Learning Outcome
After this lesson, you should be able to reduce power computation from linear time to logarithmic time.
Problem Statement
Given base, exp, and mod, return base raised to exp modulo mod.
| Input | Output | Why |
|---|---|---|
base = 2, exp = 10, mod = 1000000007 | 1024 | 2 raised to 10 is 1024, and it is smaller than the modulus. |
Brute Force Approach
Multiply base into the answer exp times. This is O(exp) and can overflow without frequent modulo.
Optimized Approach
Use exponent bits. If the current bit is 1, multiply result by base. Square base every step and halve exp.
Exact Pseudocode
result = 1 % mod
base = base % mod
while exp > 0:
if exp is odd:
result = (result * base) % mod
base = (base * base) % mod
exp = exp // 2
return resultReference Code
class Solution:
def modPow(self, base, exp, mod):
result = 1 % mod
base %= mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return resultSample Dry Run
| Step | State | Result |
|---|---|---|
| Start | result = 1, base = 2, exp = 10 | 10 is even |
| Square | base = 4, exp = 5 | now odd |
| Multiply | result = 4, base = 16, exp = 2 | bit was 1 |
| Finish | after final odd bit, result = 1024 | return 1024 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(log exp) | The exponent is halved each loop. |
| Space | O(1) | Only result, base, and exp are stored. |
Edge Cases
- exp = 0 should return 1 modulo mod.
- Take modulo after every multiplication.
- mod should be positive in normal interview versions.
Interview Checklist
- Initialize result as 1 modulo mod.
- Multiply result only when the current exponent bit is 1.
- Square base and shift exponent each loop.
FAQs
Why does halving the exponent work?
Each step consumes one binary bit of the exponent while squaring the base for the next power of two.
Why take modulo every step?
It keeps values bounded and preserves the final modulo result.
What is the core pattern?
Binary exponentiation.