Super Pow - Practice Coding Problems

Super Pow - Problem

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

For example, if a = 2 and b = [3], then b represents the number 3, so we need to calculate 2^3 mod 1337 = 8.

If a = 2 and b = [1,0], then b represents the number 10, so we need to calculate 2^10 mod 1337 = 1024.

Note: a and elements of b are guaranteed to be positive integers.

Input & Output

Example 1 — Basic Single Digit

$ Input: a = 2, b = [3]

› Output: 8

💡 Note: b represents the number 3, so we calculate 2^3 mod 1337 = 8 mod 1337 = 8

Example 2 — Multi-digit Exponent

$ Input: a = 2, b = [1,0]

› Output: 1024

💡 Note: b represents the number 10, so we calculate 2^10 mod 1337 = 1024 mod 1337 = 1024

Example 3 — Large Base with Modulo Effect

$ Input: a = 2147483647, b = [2]

› Output: 1198

💡 Note: Large base: (2147483647^2) mod 1337. First reduce base: 2147483647 mod 1337 = 1198, then 1198^2 mod 1337 = 1198

Constraints

1 ≤ a ≤ 2³¹ - 1
1 ≤ b.length ≤ 2000
0 ≤ b[i] ≤ 9
b does not contain leading zeros except for the number 0 itself

Visualization

Tap to expand

Understanding the Visualization

Input

Base a=2, exponent b=[1,0] representing 10

Process

Use modular exponentiation to compute 2^10 mod 1337

Output

Result is 1024

Key Takeaway

🎯 Key Insight: Use modular exponentiation with digit-by-digit processing to handle arbitrarily large exponents efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use modular exponentiation properties to handle extremely large exponents efficiently. Since direct calculation of a^b is impossible when b has thousands of digits, we process the exponent digit by digit using the mathematical property a^(10x+y) = (a^x)^10 × a^y mod 1337. The optimal approach uses Chinese Remainder Theorem with factorization 1337 = 7 × 191. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Chinese Remainder Theorem Optimization	O(n)	O(1)	Optimize using CRT since 1337 = 7 × 191 (coprime factors)
Direct Calculation (Impossible)	O(b)	O(1)	Convert array to number and calculate a^b mod 1337 directly
Modular Exponentiation with Digit Processing	O(n)	O(1)	Use mathematical properties to handle large exponents efficiently

Chinese Remainder Theorem Optimization — Algorithm Steps

Factorize 1337 = 7 × 191
Compute a^b mod 7 and a^b mod 191 separately
Use Euler's theorem: a^φ(m) ≡ 1 (mod m)
Combine results using Chinese Remainder Theorem

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Problem

Compute a^b mod 7 and a^b mod 191 separately

Use Euler's Theorem

Apply φ(7)=6, φ(191)=190 for optimization

Combine with CRT

Merge results to get final answer mod 1337

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int powmod(long long base, int exp, int mod) {
    if (mod == 1) return 0;
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp /= 2;
        base = (base * base) % mod;
    }
    return result;
}

int helper(int a, int* b, int bSize, int mod, int eulerMod) {
    if (bSize == 0 || (bSize == 1 && b[0] == 0)) {
        return 1;
    }
    
    int expMod = 0;
    for (int i = 0; i < bSize; i++) {
        expMod = (expMod * 10 + b[i]) % eulerMod;
    }
    expMod += eulerMod;
    
    return powmod(a, expMod, mod);
}

int solution(int a, int* b, int bSize) {
    if (bSize == 0 || (bSize == 1 && b[0] == 0)) {
        return 1;
    }
    
    a = a % 1337;
    if (a == 0) return 0;
    
    int mod7 = helper(a, b, bSize, 7, 6);
    int mod191 = helper(a, b, bSize, 191, 190);
    
    return (mod7 + 7 * ((mod191 - mod7 + 191) * 164 % 191)) % 1337;
}

int main() {
    int a;
    scanf("%d", &a);
    
    char line[1000];
    scanf(" %s", line);
    
    int b[1000];
    int bSize = 0;
    char* ptr = line + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        b[bSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(a, b, bSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Process each digit once, with constant time CRT operations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for CRT calculations

✓ Linear Space

89.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Chinese Remainder Theorem Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler