You are given a 0-indexed 2D array variables where variables[i] = [ai, bi, ci, mi], and an integer target.
An index i is good if the following formula holds:
0 <= i < variables.length((aibi % 10)ci) % mi == targetReturn an array consisting of good indices in any order.
Example 1:
Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2 Output: [0,2] Explanation: For each index i in the variables array: 1) For the index 0, variables[0] = [2,3,3,10], (23 % 10)3 % 10 = 2. 2) For the index 1, variables[1] = [3,3,3,1], (33 % 10)3 % 1 = 0. 3) For the index 2, variables[2] = [6,1,1,4], (61 % 10)1 % 4 = 2. Therefore we return [0,2] as the answer.
Example 2:
Input: variables = [[39,3,1000,1000]], target = 17 Output: [] Explanation: For each index i in the variables array: 1) For the index 0, variables[0] = [39,3,1000,1000], (393 % 10)1000 % 1000 = 1. Therefore we return [] as the answer.
Constraints:
1 <= variables.length <= 100variables[i] == [ai, bi, ci, mi]1 <= ai, bi, ci, mi <= 1030 <= target <= 103Problem Overview: You receive an array variables where each element contains four integers [a, b, c, m]. For every entry, compute ((a^b % 10)^c) % m and return the indices where the result equals a given target. The challenge is evaluating exponentiation safely without overflow while processing multiple entries.
Approach 1: Naive Simulation (O(n * (b + c)) time, O(1) space)
Iterate through each element in the array and simulate the exponentiation directly. Compute a^b with repeated multiplication, take % 10, then raise the result to the power c and apply % m. This works because the first modulus keeps numbers small, but repeated multiplication still makes the runtime proportional to b + c. It is easy to implement and mirrors the mathematical expression step by step, making it a reasonable baseline for understanding the problem.
Approach 2: Optimized Modular Exponentiation (O(n * (log b + log c)) time, O(1) space)
The efficient solution applies fast exponentiation from modular arithmetic. Instead of multiplying a by itself b times, compute a^b % 10 using binary exponentiation. This technique repeatedly squares the base and halves the exponent, reducing the complexity from linear to logarithmic. After obtaining the first modular result, apply the same fast exponentiation method again to compute (result^c) % m. The algorithm runs in logarithmic time per exponent and avoids large intermediate numbers, which makes it the preferred method for problems involving repeated powers and mod operations.
The process is mostly simulation combined with careful math optimization. Each element is processed independently, so the algorithm scales linearly with the number of rows in the input.
Recommended for interviews: Interviewers expect the optimized modular exponentiation approach. Starting with the naive simulation shows you understand the formula, but switching to binary exponentiation demonstrates knowledge of efficient power computation and modular arithmetic. This optimization reduces exponent handling from linear to logarithmic time, which is a common requirement in coding interviews involving large powers.
This approach involves direct computation of the formula for each index. We iterate over each variable, compute the exponential terms, and check if the result matches the target.
The function iterates through the variables list and computes the value of the formula using Python's built-in pow function for modular exponentiation. If the result equals the target, the index is considered good and appended to the result list.
Time Complexity: O(n * b * c), because we calculate exponential values directly.
Space Complexity: O(1), as we do not use any extra space apart from storing results.
This approach leverages the method of modular exponentiation which allows efficient computation of large powers mod m. Instead of computing power directly, it uses recursion or iterative squaring.
The function mod_exp implements modular exponentiation by squaring. This reduces time complexity and efficiently computes large powers. For each variable, we compute the intermediate power modulo 10 and apply the method again for modulus m computation.
Time Complexity: O(n * log(b) + log(c)), where n is the number of equations.
Space Complexity: O(1), marginal storage required beyond result.
We can directly simulate according to the problem description. For the power operation modulo, we can use the fast power method to speed up the calculation.
The time complexity is O(n times log M), where n is the length of the array variables; and M is the maximum value in b_i and c_i, in this problem M \le 10^3. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n * b * c), because we calculate exponential values directly. |
| Optimized Modular Exponentiation | Time Complexity: O(n * log(b) + log(c)), where n is the number of equations. |
| Simulation + Fast Power | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation | O(n * (b + c)) | O(1) | Useful for understanding the formula or when exponents are very small |
| Optimized Modular Exponentiation | O(n * (log b + log c)) | O(1) | General case with large exponents; avoids overflow and improves performance |
2961 Double Modular Exponentiation || Exponentiation 🔥 • Ayush Rao • 577 views views
Watch 7 more video solutions →Practice Double Modular Exponentiation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor