2961. Double Modular Exponentiation

MediumArrayMathSimulation

Problem Description

You are given a 2D array variables where each element variables[i] contains four integers: [a_i, b_i, c_i, m_i]. You also have an integer target.

Your task is to find all indices i that are "good". An index i is considered good if it satisfies both conditions:

It's a valid index: 0 <= i < variables.length
The following mathematical formula evaluates to true: ((a_i^b_i % 10)^c_i) % m_i == target

Breaking down the formula:

First, calculate a_i raised to the power of b_i
Take the result modulo 10 to get the last digit
Raise this last digit to the power of c_i
Take the final result modulo m_i
Check if this equals the target

The solution uses Python's built-in pow function with three arguments pow(base, exponent, modulus) which efficiently computes (base^exponent) % modulus using fast exponentiation. The nested pow calls handle the two-step calculation: first computing (a^b) % 10, then using that result as the base for (result^c) % m.

Return a list containing all the good indices in any order.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The problem asks us to evaluate a mathematical expression for each element in the array and check if it equals the target. The straightforward approach is to iterate through each element and compute the formula exactly as specified.

The key insight is recognizing that we're dealing with modular exponentiation, which can be computationally expensive if done naively. For example, calculating a^b directly could result in an extremely large number before taking modulo 10, which is inefficient and could cause overflow issues.

The solution leverages Python's built-in pow(base, exp, mod) function, which implements fast modular exponentiation. This function computes (base^exp) % mod efficiently without calculating the full value of base^exp first.

For our formula ((a^b % 10)^c) % m, we can break it into two modular exponentiation steps:

First step: pow(a, b, 10) gives us a^b % 10 (the last digit of a^b)
Second step: pow(result_from_step1, c, m) gives us the final result

By nesting these two pow calls as pow(pow(a, b, 10), c, m), we efficiently compute the entire expression. We then simply check if this equals the target and collect all indices where this condition holds true.

The list comprehension approach makes the code concise - we enumerate through the variables array to get both the index and values, unpack the four values from each element, compute the formula, and include the index in our result list only if the computation matches the target.

Learn more about Math patterns.

Solution Approach

The solution uses simulation combined with fast power (modular exponentiation) to efficiently compute the required formula for each element.

Implementation Steps:

Iterate through the array with enumeration: We use enumerate(variables) to get both the index i and the values (a, b, c, m) from each element simultaneously.
Apply fast modular exponentiation: For each element, we compute the formula using nested pow calls:
- Inner pow(a, b, 10): Computes (a^b) % 10 using fast power algorithm. This gives us the last digit of a^b without calculating the potentially huge value of a^b directly.
- Outer pow(result, c, m): Takes the result from the inner computation and raises it to power c, then takes modulo m.
Filter good indices: We check if pow(pow(a, b, 10), c, m) == target. If true, the index i is included in the result list.

List comprehension pattern: The entire solution is implemented as a single list comprehension:

[i for i, (a, b, c, m) in enumerate(variables) if pow(pow(a, b, 10), c, m) == target]

This pattern efficiently builds the result list in one pass through the data.

Why Fast Power? The fast power algorithm (built into Python's pow with three arguments) uses the property that (a * b) % m = ((a % m) * (b % m)) % m. It computes large exponentiations by:

Breaking down the exponent into binary representation
Repeatedly squaring and taking modulo at each step
This reduces time complexity from O(n) to O(log n) for computing a^n % m

The solution is optimal with O(n) time complexity where n is the length of the variables array, as we must check each element exactly once.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Example Input:

variables = [[2, 3, 3, 10], [3, 3, 3, 1], [6, 1, 1, 4]]
target = 2

We need to find all indices where ((a^b % 10)^c) % m == target.

Step-by-step evaluation:

Index 0: [2, 3, 3, 10]

a=2, b=3, c=3, m=10
First, calculate pow(2, 3, 10):
- 2^3 = 8
- 8 % 10 = 8
Then, calculate pow(8, 3, 10):
- 8^3 = 512
- 512 % 10 = 2
Result: 2 == target (2) ✓ This index is good!

Index 1: [3, 3, 3, 1]

a=3, b=3, c=3, m=1
First, calculate pow(3, 3, 10):
- 3^3 = 27
- 27 % 10 = 7
Then, calculate pow(7, 3, 1):
- 7^3 = 343
- 343 % 1 = 0 (any number mod 1 is 0)
Result: 0 != target (2) ✗ This index is not good

Index 2: [6, 1, 1, 4]

a=6, b=1, c=1, m=4
First, calculate pow(6, 1, 10):
- 6^1 = 6
- 6 % 10 = 6
Then, calculate pow(6, 1, 4):
- 6^1 = 6
- 6 % 4 = 2
Result: 2 == target (2) ✓ This index is good!

Final Answer: [0, 2]

The solution efficiently computes these values using nested pow calls in a list comprehension, avoiding the need to calculate large intermediate values like 8^3 = 512 directly, instead computing the modulo at each step.

Solution Implementation

1from typing import List
2
3class Solution:
4    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
5        """
6        Find indices where the double modular exponentiation equals the target.
7      
8        For each variable [a, b, c, m], calculate ((a^b mod 10)^c mod m).
9        Return indices where this result equals the target.
10      
11        Args:
12            variables: List of [a, b, c, m] integer quadruples
13            target: The target value to match
14          
15        Returns:
16            List of indices where the calculation equals target
17        """
18        result_indices = []
19      
20        # Iterate through each variable set with its index
21        for index, variable_set in enumerate(variables):
22            # Unpack the four values from the current variable set
23            base = variable_set[0]  # a
24            first_exponent = variable_set[1]  # b
25            second_exponent = variable_set[2]  # c
26            final_modulus = variable_set[3]  # m
27          
28            # Calculate (a^b mod 10)
29            intermediate_result = pow(base, first_exponent, 10)
30          
31            # Calculate ((a^b mod 10)^c mod m)
32            final_result = pow(intermediate_result, second_exponent, final_modulus)
33          
34            # Check if the result matches the target
35            if final_result == target:
36                result_indices.append(index)
37      
38        return result_indices
39

1class Solution {
2    /**
3     * Finds all indices where the formula ((a^b % 10)^c % m) equals target.
4     * 
5     * @param variables A 2D array where each row contains [a, b, c, m]
6     * @param target The target value to match
7     * @return List of indices where the formula equals target
8     */
9    public List<Integer> getGoodIndices(int[][] variables, int target) {
10        List<Integer> resultIndices = new ArrayList<>();
11      
12        // Iterate through each variable set
13        for (int i = 0; i < variables.length; i++) {
14            int[] currentVariable = variables[i];
15            int base = currentVariable[0];
16            int firstExponent = currentVariable[1];
17            int secondExponent = currentVariable[2];
18            int modulus = currentVariable[3];
19          
20            // Calculate (base^firstExponent % 10)
21            int intermediateResult = quickPower(base, firstExponent, 10);
22          
23            // Calculate (intermediateResult^secondExponent % modulus)
24            int finalResult = quickPower(intermediateResult, secondExponent, modulus);
25          
26            // Check if the result matches the target
27            if (finalResult == target) {
28                resultIndices.add(i);
29            }
30        }
31      
32        return resultIndices;
33    }
34
35    /**
36     * Calculates (base^exponent) % modulus using fast exponentiation.
37     * Uses binary exponentiation to efficiently compute large powers.
38     * 
39     * @param base The base number
40     * @param exponent The power to raise the base to
41     * @param modulus The modulus for the operation
42     * @return The result of (base^exponent) % modulus
43     */
44    private int quickPower(long base, int exponent, int modulus) {
45        long result = 1;
46      
47        // Binary exponentiation algorithm
48        while (exponent > 0) {
49            // If the current bit is 1, multiply result by base
50            if ((exponent & 1) == 1) {
51                result = (result * base) % modulus;
52            }
53          
54            // Square the base for the next bit position
55            base = (base * base) % modulus;
56          
57            // Shift right to process the next bit
58            exponent >>= 1;
59        }
60      
61        return (int) result;
62    }
63}
64

1class Solution {
2public:
3    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
4        vector<int> result;
5      
6        // Lambda function to calculate (base^exponent) % modulus using fast exponentiation
7        auto modularPower = [&](long long base, int exponent, int modulus) {
8            long long result = 1;
9          
10            // Binary exponentiation algorithm
11            while (exponent > 0) {
12                // If exponent is odd, multiply result with base
13                if (exponent & 1) {
14                    result = (result * base) % modulus;
15                }
16                // Square the base and halve the exponent
17                base = (base * base) % modulus;
18                exponent >>= 1;
19            }
20          
21            return static_cast<int>(result);
22        };
23      
24        // Iterate through each variable set
25        for (int i = 0; i < variables.size(); ++i) {
26            // Extract values from current variable set
27            vector<int>& currentVariable = variables[i];
28            int a = currentVariable[0];
29            int b = currentVariable[1];
30            int c = currentVariable[2];
31            int m = currentVariable[3];
32          
33            // Calculate ((a^b mod 10)^c mod m)
34            // First: calculate a^b mod 10
35            int innerResult = modularPower(a, b, 10);
36            // Second: calculate (innerResult)^c mod m
37            int finalResult = modularPower(innerResult, c, m);
38          
39            // Check if the result equals target
40            if (finalResult == target) {
41                result.push_back(i);
42            }
43        }
44      
45        return result;
46    }
47};
48

1/**
2 * Finds indices of variables that satisfy the power equation condition
3 * @param variables - Array of variable sets, each containing [a, b, c, m]
4 * @param target - Target value to match
5 * @returns Array of indices where ((a^b mod 10)^c mod m) equals target
6 */
7function getGoodIndices(variables: number[][], target: number): number[] {
8    /**
9     * Calculates (base^exponent) mod modulo using fast exponentiation
10     * Uses BigInt to prevent overflow during multiplication
11     * @param base - Base number
12     * @param exponent - Power to raise the base to
13     * @param modulo - Modulo value
14     * @returns Result of (base^exponent) mod modulo
15     */
16    const quickPower = (base: number, exponent: number, modulo: number): number => {
17        let result = 1;
18      
19        // Process each bit of the exponent
20        while (exponent > 0) {
21            // If current bit is 1, multiply result by base
22            if (exponent & 1) {
23                result = Number((BigInt(result) * BigInt(base)) % BigInt(modulo));
24            }
25            // Square the base for the next bit position
26            base = Number((BigInt(base) * BigInt(base)) % BigInt(modulo));
27            // Right shift to process the next bit
28            exponent >>= 1;
29        }
30      
31        return result;
32    };
33  
34    const goodIndices: number[] = [];
35  
36    // Check each variable set
37    for (let index = 0; index < variables.length; index++) {
38        const [a, b, c, m] = variables[index];
39      
40        // Calculate (a^b mod 10) first, then raise it to power c mod m
41        const innerPower = quickPower(a, b, 10);
42        const finalResult = quickPower(innerPower, c, m);
43      
44        // Add index to result if it matches the target
45        if (finalResult === target) {
46            goodIndices.push(index);
47        }
48    }
49  
50    return goodIndices;
51}
52

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array variables and M is the maximum value among b_i and c_i.

The algorithm iterates through all n elements in the variables array. For each element, it performs two modular exponentiation operations using Python's built-in pow function with three arguments:

pow(a, b, 10) computes (a^b) mod 10
pow(result, c, m) computes (result^c) mod m

The pow function with three arguments uses fast modular exponentiation (binary exponentiation), which has a time complexity of O(log exponent). Therefore:

The first pow operation takes O(log b)
The second pow operation takes O(log c)

Since we perform these operations for each of the n elements, and M represents the maximum value of b and c (where M ≤ 10^3 in this problem), the overall time complexity is O(n × log M).

The space complexity is O(1) if we don't count the output list. The algorithm only uses a constant amount of extra space for the loop variables i, a, b, c, and m, regardless of the input size. The list comprehension creates an output list, but this is typically not counted in space complexity analysis as it's part of the required output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Operations

A common mistake is misunderstanding the formula's parentheses and applying operations in the wrong order. Some might incorrectly compute it as:

(a^b) % (10^c) % m
a^(b % 10)^c % m
((a^b) % 10^c) % m

Solution: Carefully parse the formula: First compute a^b, take modulo 10, then raise that result to power c, and finally take modulo m. The correct implementation is:

step1 = pow(a, b, 10)  # (a^b) % 10
step2 = pow(step1, c, m)  # (step1^c) % m

2. Not Using Modular Exponentiation

Computing large powers directly without modular arithmetic can cause integer overflow or be extremely slow:

# WRONG - Can overflow or timeout
result = ((a ** b) % 10) ** c % m

Solution: Always use Python's three-argument pow(base, exp, mod) function which implements fast modular exponentiation:

# CORRECT - Efficient and no overflow
pow(pow(a, b, 10), c, m)

3. Edge Case: Modulus of 1

When m = 1, any number modulo 1 equals 0. If target is non-zero and m = 1, that index cannot be good, but this might not be immediately obvious.

Solution: The code handles this naturally since pow(x, c, 1) will always return 0, which will only match target if target is also 0.

4. Zero Base with Zero Exponent

The case where a = 0 and b = 0 results in 0^0, which mathematically is undefined but Python evaluates as 1.

Solution: Python's pow(0, 0) returns 1 by convention, which is consistent with most programming languages. Be aware that:

pow(0, 0, 10) == 1  # This is true in Python

5. Assuming Target Must Be Less Than m

Some might assume that since we're taking modulo m, the target must be in range [0, m-1]. However, the target can be any value, and we still need to check equality.

Solution: Direct equality comparison works correctly regardless of target's value. If target >= m, it simply won't match any result from pow(x, c, m) which is always in range [0, m-1].

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

I don't know