Compute (base ** exp) % mod for non-negative integers base, exp, and a positive integer mod. The exponent exp…

Question

Compute (base ** exp) % mod for non-negative integers base, exp, and a positive integer mod. The exponent exp can be as large as 10^9, so you cannot multiply exp times in a loop, and base**exp itself is far too large to materialize. Return the result as an integer in [0, mod). Note that when mod == 1 the answer is always 0.

Prep Room · Answer

**Intuition** We need base^exp mod m where exp can be a billion, so a linear loop is too slow and base^exp is astronomically large. Binary exponentiation…

Modular exponentiation