Medium · Binary Exponentiation
Understand → Visualise → Practice.
Return base raised to the non-negative exponent modulo the positive modulus without constructing the full power.
Write the exponent in binary. Square the base each step and multiply it into the result when the current bit is 1, reducing mod m every time.
result = 1 % modulus (so modulus 1 gives 0), base %= modulus.
If the lowest exponent bit is 1, result = result × base % modulus; then base = base² % modulus.
exponent >>= 1, until it reaches 0.
O(log exponent) time and O(1) space.
Delaying the modulus until the end creates enormous intermediate values.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.