Double Modular Exponentiation - Practice Coding Problems

Double Modular Exponentiation - Problem

You are given a 0-indexed 2D array variables where variables[i] = [a_i, b_i, c_i, m_i], and an integer target.

An index i is good if the following formula holds:

((a_i^b_i % 10)^c_i) % m_i == target

Return an array consisting of good indices in any order.

Input & Output

Example 1 — Basic Case

$ Input: variables = [[2,3,3,10],[3,1,4,12],[7,3,1,17],[4,2,5,5]], target = 3

› Output: [2]

💡 Note: For index 2: ((7³ % 10)¹) % 17 = (343 % 10)¹ % 17 = 3¹ % 17 = 3. Only index 2 matches target 3.

Example 2 — Multiple Matches

$ Input: variables = [[39,3,1000,1000]], target = 49

› Output: [0]

💡 Note: For index 0: ((39³ % 10)¹⁰⁰⁰) % 1000 = (59319 % 10)¹⁰⁰⁰ % 1000 = 9¹⁰⁰⁰ % 1000 = 49.

Example 3 — No Matches

$ Input: variables = [[2,2,2,2]], target = 5

› Output: []

💡 Note: For index 0: ((2² % 10)²) % 2 = (4²) % 2 = 16 % 2 = 0 ≠ 5. No indices match.

Constraints

1 ≤ variables.length ≤ 1000
variables[i] = [a_i, b_i, c_i, m_i]
1 ≤ a_i, b_i, c_i, m_i ≤ 10⁶
0 ≤ target ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

2D array of variables and target value

Process

Apply double modular exponentiation formula to each row

Output

Array of indices where formula equals target

Key Takeaway

🎯 Key Insight: Use modular exponentiation to efficiently handle large powers while preventing integer overflow

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use modular exponentiation to efficiently compute very large powers without overflow. We apply the formula ((a^b % 10)^c) % m for each variable set and collect indices where the result equals the target. Best approach uses binary exponentiation: Time: O(n × log(max(b,c))), Space: O(k) where k is the number of matches.

Common Approaches

Approach	Time	Space	Notes
✓ Direct Calculation with Modular Exponentiation	O(n × (log b + log c))	O(k)	Calculate each formula using built-in power functions with modular arithmetic
Optimized Modular Exponentiation	O(n × (log b + log c))	O(k)	Use efficient binary exponentiation to handle very large exponents

Direct Calculation with Modular Exponentiation — Algorithm Steps

Step 1: For each variables[i], extract [a, b, c, m]
Step 2: Calculate first_result = a^b % 10 using modular exponentiation
Step 3: Calculate final_result = first_result^c % m using modular exponentiation
Step 4: If final_result equals target, add index i to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Variables

Get [a, b, c, m] from each row

First Modular Exponentiation

Calculate a^b % 10

Second Modular Exponentiation

Calculate (result)^c % m

Check Target

Compare with target and collect indices

Code -

solution.c — C

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

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

int* solution(int variables[][4], int variablesSize, int target, int* returnSize) {
    int* goodIndices = (int*)malloc(variablesSize * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < variablesSize; i++) {
        int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
        long long firstResult = modPow(a, b, 10);
        long long finalResult = modPow(firstResult, c, m);
        if (finalResult == target) {
            goodIndices[(*returnSize)++] = i;
        }
    }
    
    return goodIndices;
}

int main() {
    int variables[1000][4];
    int variablesSize = 0;
    int target;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[a,b,c,d],[e,f,g,h],...]
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            sscanf(ptr, "[%d,%d,%d,%d]", 
                   &variables[variablesSize][0], 
                   &variables[variablesSize][1], 
                   &variables[variablesSize][2], 
                   &variables[variablesSize][3]);
            variablesSize++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr) ptr++;
        }
        ptr++;
    }
    
    scanf("%d", &target);
    
    int returnSize;
    int* result = solution(variables, variablesSize, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × (log b + log c))

For n variables, each requiring O(log b) + O(log c) for two modular exponentiations

⚡ Linearithmic

Space Complexity

O(k)

Where k is the number of good indices stored in result array

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Direct Calculation with Modular Exponentiation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler