Power Under A Modulus
Problem
Compute base raised to exp, reported modulo mod, where the exponent can reach a billion. Building the power first and reducing afterwards would produce a number with hundreds of millions of digits, so the reduction has to happen along the way.
Examples
Input: base = 2, exp = 10, mod = 1000
Output: 24
Why: 1024 % 1000Input: base = 7, exp = 1000000, mod = 13
Output: 9Input: base = 5, exp = 3, mod = 1
Output: 0
Why: edge case, everything is congruent to 0 modulo 1Hints
0 / 3
Multiplying one factor at a time costs one step per unit of the exponent, which is hopeless here — the exponent needs to shrink, not count down.
Squaring doubles an exponent in a single multiplication, and any exponent can be written as a sum of powers of two.
Walk the binary digits of the exponent from the bottom. Keep a running value that starts at the base and squares every round, and multiply it into the answer whenever the current digit is one. Reduce by the modulus after each multiplication so nothing ever grows past its square.
Solution
Reading the exponent in binary turns it into a sum of powers of two, and each of those powers is one squaring away from the last. So the running base climbs the ladder, and the answer picks up the rungs whose binary digit is set. Because a remainder survives multiplication, reducing after every step keeps every intermediate value below the square of the modulus without changing the result. Time is O(log exp), and space is O(1).
def mod_power(base, exp, mod):
if mod == 1:
return 0 # every value is congruent to 0
result, base = 1, base % mod
while exp:
if exp & 1: # this binary digit is set
result = result * base % mod
base = base * base % mod # climb: b, b², b⁴, b⁸ ...
exp >>= 1
return result
print(mod_power(2, 10, 1000)) # -> 24
print(mod_power(7, 1000000, 13)) # -> 9
print(mod_power(5, 3, 1)) # -> 0
print(mod_power(3, 0, 7)) # -> 1Stuck on the idea rather than the code? Fast Exponentiation covers it.