Modular Power by Squaring
MediumMath & Geometry
Problem
A key-exchange routine needs base raised to exponent, reduced modulo modulus. The exponent can be as large as 10^15, so multiplying exponent times is out of the question.
Return base^exponent mod modulus. Treat any number to the power 0 as 1 (including 0^0), so the answer for exponent 0 is 1 mod modulus.
Example 1
- Input:
- base = 2, exponent = 10, modulus = 1000
- Output:
- 24
2^10 = 1024 and 1024 mod 1000 = 24.
Example 2
- Input:
- base = 5, exponent = 3, modulus = 13
- Output:
- 8
125 = 9 · 13 + 8.
Example 3
- Input:
- base = 3, exponent = 0, modulus = 7
- Output:
- 1
Constraints
- 0 ≤ base ≤ 10^9
- 0 ≤ exponent ≤ 10^15
- 1 ≤ modulus ≤ 10^9 + 7
Hint
Show the first hint
Multiplying base by itself exponent times is 10^15 steps. Can you reuse squares?
Walkthrough
How to approach it
01Clarify before coding
- What is 0^0? Defined as 1 here, so exponent 0 always gives 1 mod modulus.
- Can modulus be 1? Yes: every answer is then 0, including for exponent 0.
- How big can intermediate products get? Two residues below 10^9 + 7 multiply to about 10^18, beyond JavaScript's safe 2^53, so use BigInt there (Python ints are unbounded).
02Brute force
Start from 1 and multiply by base exponent times, reducing modulo each time.
Cost: O(exponent) multiplications: 10^15 steps, hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.