Power With a Written-Out Exponent
MediumMath & Geometry
Problem
A puzzle gives you a base and an exponent written out as a decimal string exponentDigits that can have thousands of digits, far too large for any integer type.
Return base^E mod modulus, where E is the number written in exponentDigits. Treat any power with exponent 0 as 1, so the answer for E = 0 is 1 mod modulus.
Example 1
- Input:
- base = 2, exponentDigits = "10", modulus = 1000
- Output:
- 24
2^10 = 1024, which leaves 24.
Example 2
- Input:
- base = 3, exponentDigits = "200", modulus = 50
- Output:
- 1
Example 3
- Input:
- base = 0, exponentDigits = "0", modulus = 3
- Output:
- 1
Constraints
- 0 ≤ base ≤ 10^9
- 1 ≤ exponentDigits.length ≤ 10^4, digits only, no leading zeros unless the string is "0"
- 1 ≤ modulus ≤ 10^7
Hint
Show the first hint
You cannot turn the exponent into a number, but you can read it one digit at a time, left to right.
Walkthrough
How to approach it
01Clarify before coding
- Is the exponent always a valid non-negative decimal? Yes, digits only.
- Can modulus be 1? Yes: every answer is 0.
- Can I reduce the exponent modulo φ(modulus) using Euler's theorem? Only when base and modulus are coprime, which is not guaranteed here, so avoid it.
- How large are intermediate products? Two residues below 10^7 multiply to below 10^14, safe for JavaScript numbers.
02Brute force
Convert the string to a big integer and run ordinary fast exponentiation, or multiply E times.
Cost: Multiplying E times is astronomically slow; big-integer conversion works in Python but not in languages without big integers, and its binary expansion still costs O(L²) to build.
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.