276. Super Modular Power
You must compute a raised to a gigantic power, modulo 1337. The exponent is far too large for any built-in integer, so it arrives as exponentDigits: its decimal digits, most significant first, with no leading zero. For instance [2, 0, 3] stands for the exponent 203.
Return a^e mod 1337, where e is the number written by exponentDigits. The exponent is always at least 1, and may have up to 2000 digits, so repeating multiplications e times is hopeless. Aim for O(len(exponentDigits)) time with O(1) extra space, by treating the digits one at a time.
Example 1
- Input:
- a = 9, exponentDigits = [4]
- Output:
- 1213
- Explanation:
9^4 = 6561 and 6561 mod 1337 = 1213.
Example 2
- Input:
- a = 5, exponentDigits = [2,0,3]
- Output:
- 542
- Explanation:
The exponent digits spell 203, so the value is 5^203 mod 1337.
Example 3
- Input:
- a = 2674, exponentDigits = [7,7]
- Output:
- 0
- Explanation:
2674 is a multiple of 1337, so every positive power is 0 modulo 1337.
Constraints
1 ≤ a ≤ 231 - 1
1 ≤ exponentDigits.length ≤ 2000
0 ≤ exponentDigits[i] ≤ 9, exponentDigits[0] ≠ 0 (so the exponent is at least 1)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(len)
- Space
- O(1)