Given a positive integer a and a very large positive integer b, where b is represented as an array of digits, return: ab % 1337 The array b stores the digits of the exponent in normal order.
For example: b = [1, 2, 3] means the exponent is 123.
Example 1
Input: a = 2, b = [3]
Output: 8
Explanation: 23 = 8 , and 8 % 1337 = 8.
Example 2
Input: a = 2, b = [1, 0]
Output: 1024
Explanation: b = [1, 0] means the exponent is 10. So: 210 = 1024 And: 1024 % 1337 = 1024
Approach
The exponent is too large to convert into an integer. But the digits of the exponent can still be used one by one. Suppose some digits have already formed an exponent x. Now a new digit d comes at the end. The new exponent becomes: 10 * x + d
So: a(10x + d) = (ax)10 * ad This is the key observation. It means after reading each digit, the current answer can be updated by raising the old answer to power 10, then multiplying it by a raised to the new digit. Since every operation is done modulo 1337, the values never become huge.
Algorithm
Store
MOD = 1337, because the problem specifically asks for the answer modulo1337.Reduce
ausinga % MOD. This is done because only the remainder matters in modular multiplication.Keep
result = 1. At the beginning, no digit has been processed, so the effective exponent is0, and a0 = 1.For every digit in
b, update the old exponent logic. If the old exponent wasxand the new digit isd, the new exponent becomes10x + d.Compute result10 % MOD because all earlier digits shift one decimal place to the left.
Compute adigit % MOD because the current digit contributes its own small power.
Multiply both parts under modulo. This gives the result for all digits processed so far.
Use fast modular exponentiation for power calculation so every power operation stays quick and safe.
Dry Run
Super Pow Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: static const int MOD = 1337; /* * Computes base raised to exponent under modulo MOD. * Binary exponentiation keeps the value small and fast. */ int modularPower(int base, int exponent) { // The result starts as 1 because multiplying by 1 changes nothing. long long result = 1; // Reducing the base first prevents large intermediate values. long long currentBase = base % MOD; // Binary exponentiation processes the exponent bit by bit. while (exponent > 0) { // If the current bit is set, this power contributes to the answer. if (exponent % 2 == 1) { result = (result * currentBase) % MOD; } // Squaring prepares the base for the next binary place. currentBase = (currentBase * currentBase) % MOD; // Dividing by 2 moves to the next bit of the exponent. exponent /= 2; } return (int)result; }public: /* * Computes a raised to the very large exponent b, * where b is stored as digits, and returns modulo 1337. */ int superPow(int a, vector<int>& b) { // Only the remainder of a matters in modular arithmetic. int base = a % MOD; // This stores the answer for the digits processed so far. int result = 1; for (int digit : b) { // Old exponent shifts left by one decimal place, // so the previous answer must be raised to power 10. int shiftedPart = modularPower(result, 10); // The current digit adds a small extra power of a. int digitPart = modularPower(base, digit); // Both parts together represent a^(oldExponent * 10 + digit). result = (shiftedPart * digitPart) % MOD; } return result; }};// Driver code startsint main() { Solution solution; int a = 2; vector<int> b = {1, 0}; cout << solution.superPow(a, b) << endl; return 0;}Complexity Analysis
Time Complexity: O(n * log 10), where n is the number of digits in b. Since each digit needs two small modular exponentiation calls, this is practically linear.
Space Complexity: O(1) because constant extra space is used.
Interview follow-up Questions
Because b can contain up to thousands of digits. Such a number may not fit in normal integer types, and even languages with big integers would make the solution heavier than needed.
Be the first to add a comment.