Watch 8 video solutions for Double Modular Exponentiation, a medium level problem involving Array, Math, Simulation. This walkthrough by Ayush Rao has 577 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |