Evaluate power and modulo expression using fast power
Filed under SAP
Free read 1 of 3Confirm constraints on inputs to prevent integer overflow.
The question
Implement modular exponentiation to efficiently compute (base^exp) % mod.
Constraints
- 0 <= base, exp <= 10^9
- 1 <= mod <= 10^9
Examples
- Input
- base = 2, exp = 10, mod = 1000
- Output
- 24
- Why
- 2^10 = 1024, and 1024 % 1000 = 24.
Approach
Confirm constraints on inputs to prevent integer overflow.
Multiply the base 'exp' times iteratively, taking modulo at each step. O(exp) time which is too slow for large exponents.
Use binary exponentiation (divide and conquer): if exp is even, compute (base^(exp/2))^2 % mod; if odd, multiply by base. Reduces time to O(log exp).
Exponent equals 0 (result should be 1 % mod), base equals 0.
Solution
O(log exp) time, O(1) space
def fast_power(base, exp, mod):
res = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
res = (res * base) % mod
base = (base * base) % mod
exp //= 2
return res
Tips
- What they are testing: Test with exp = 0, mod = 1, and large exponents to verify logarithmic time performance.
- Common mistake: Overflow issues in languages with fixed integer sizes if modulo is not applied at each multiplication step.
Related SAP questions
Collected from public candidate posts and coding forums. Updated Nov 2026.