Modular Exponentiation

Difficulty: Medium · Topic: Math for algorithms

Compute base^exp mod m efficiently. Naively multiplying exp times is too slow for large exponents; binary exponentiation squares the base and halves the exponent, taking the modulus at every step to keep numbers small — O(log exp).

Examples

mod_pow(2, 10, 1000)
→ 24

1024 mod 1000 = 24.

mod_pow(3, 0, 7)
→ 1

Anything^0 = 1.

Target complexity: time O(log exp), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.