Double Modular Exponentiation solution and explanation
3 more videos on this problem
2961 Double Modular Exponentiation || Exponentiation 🔥Ayush Rao · 4:40 · 581 views
2961. Double Modular Exponentiation (Leetcode Medium)Programming Live with Larry · 6:17 · 216 views
Leetcode 2961 || Double Modular Exponentiation || Leetcode Weekly Challenge || MediumKomal Pal · 9:50 · 216 views
Double Modular Exponentiation - LeetCode 2961 - PythonAlpha-Code · 9:43 · 118 views
The problem
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 == target
Return 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 <= 103
Approach overview
Problem 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 1: Naive Approach
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.
def good_indices(variables, target):
result = []
for i, (a, b, c, m) in enumerate(variables):
power_mod = (pow(a, b, 10))**c % m
if power_mod == target:
result.append(i)
return result
# Example usage:
variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]]
target = 2
print(good_indices(variables, target)) # Output: [0,2]import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> goodIndices(int[][] variables, int target) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < variables.length; i++) {
int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
int powerMod = (int)Math.pow(Math.pow(a, b) % 10, c) % m;
if (powerMod == target) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] variables = {{2,3,3,10},{3,3,3,1},{6,1,1,4}};
int target = 2;
System.out.println(solution.goodIndices(variables, target)); // Output: [0,2]
}
}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.
Approach 2: Optimized Modular Exponentiation
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.
def mod_exp(base, exp, mod):
result = 1
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
exp //= 2
return result
def good_indices(variables, target):
result = []
for i, (a, b, c, m) in enumerate(variables):
intermediate = mod_exp(a, b, 10)
power_mod = mod_exp(intermediate, c, m)
if power_mod == target:
result.append(i)
return result
# Example usage:
variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]]
target = 2
print(good_indices(variables, target)) # Output: [0,2]import java.util.ArrayList;
import java.util.List;
public class Solution {
private int modExp(int base, int exp, int mod) {
int result = 1;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
public List<Integer> goodIndices(int[][] variables, int target) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < variables.length; i++) {
int a = variables[i][0], b = variables[i][1];
int c = variables[i][2], m = variables[i][3];
int intermediate = modExp(a, b, 10);
int powerMod = modExp(intermediate, c, m);
if (powerMod == target) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] variables = {{2,3,3,10},{3,3,3,1},{6,1,1,4}};
int target = 2;
System.out.println(solution.goodIndices(variables, target)); // Output: [0,2]
}
}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.
Approach 3: Simulation + Fast Power
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).
class Solution {
public:
vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
vector<int> ans;
auto qpow = [&](long long a, int n, int mod) {
long long ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return (int) ans;
};
for (int i = 0; i < variables.size(); ++i) {
auto e = variables[i];
int a = e[0], b = e[1], c = e[2], m = e[3];
if (qpow(qpow(a, b, 10), c, m) == target) {
ans.push_back(i);
}
}
return ans;
}
};function getGoodIndices(variables: number[][], target: number): number[] {
const qpow = (a: number, n: number, mod: number) => {
let ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
}
a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
}
return ans;
};
const ans: number[] = [];
for (let i = 0; i < variables.length; ++i) {
const [a, b, c, m] = variables[i];
if (qpow(qpow(a, b, 10), c, m) === target) {
ans.push(i);
}
}
return ans;
}func getGoodIndices(variables [][]int, target int) (ans []int) {
qpow := func(a, n, mod int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
for i, e := range variables {
a, b, c, m := e[0], e[1], e[2], e[3]
if qpow(qpow(a, b, 10), c, m) == target {
ans = append(ans, i)
}
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Double Modular Exponentiation easy or hard?
Double Modular Exponentiation is considered a medium difficulty problem. The main challenge is recognizing that naive exponentiation is inefficient and replacing it with binary exponentiation. Once you apply modular arithmetic correctly, the implementation becomes straightforward.
Double Modular Exponentiation Python/Java solution
Python and Java solutions typically implement a fast power function that computes (base^exp) % mod using binary exponentiation. The algorithm iteratively squares the base, multiplies when the exponent bit is set, and reduces using modulo each step. This avoids overflow and keeps numbers small throughout the computation.
How to solve Double Modular Exponentiation in O(n)?
Strict O(n) is not achievable because exponentiation depends on the size of the exponents. The practical optimal solution is O(n * (log b + log c)) using fast modular exponentiation. Each array element is processed independently while computing powers in logarithmic time.
What is the best approach for Double Modular Exponentiation?
The most efficient approach uses fast modular exponentiation (binary exponentiation). Instead of computing powers directly, it repeatedly squares the base and halves the exponent while applying modulo operations. This reduces exponent computation from O(b) to O(log b). For each array element, compute a^b % 10 and then apply fast exponentiation again for the second power.
Is Double Modular Exponentiation asked at Google/Amazon/Meta?
Problems involving modular exponentiation and fast power frequently appear in interviews at companies like Google, Amazon, and Meta. They often test understanding of binary exponentiation, overflow prevention, and modular arithmetic. Variants appear in algorithm rounds and competitive programming problems.
What data structure is used in Double Modular Exponentiation?
The problem primarily uses an array to store input values. The main focus is mathematical computation rather than complex data structures. Efficient modular arithmetic and exponentiation logic drive the solution.
What is the time complexity of Double Modular Exponentiation?
The optimized solution runs in O(n * (log b + log c)) time, where n is the number of rows in the variables array. Each exponentiation uses binary exponentiation, which processes the exponent in logarithmic time. Space complexity remains O(1) because only a few variables are maintained during computation.