Double Modular Exponentiation

Med

#2641Time: O(N * (max_b + max_c)), where `N` is the length of `variables`, `max_b` is the maximum value of `b_i`, and `max_c` is the maximum value of `c_i`. The helper function `power(base, exp, mod)` takes `O(exp)` time. For each variable set, we call it twice, with exponents `b` and `c`. Given the constraints (`b, c <= 1000`), this is efficient enough to pass.Space: O(K), where K is the number of good indices found. This is for the output list. The auxiliary space complexity is O(1).1 company

Patterns

Math

Data structures

Array

Companies

Barclays

Prompt

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:

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == 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 <= 100
variables[i] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly implements the formula by iterating through each set of variables. For each set [a, b, c, m], it calculates the two modular exponentiations required: (a^b) % 10 and (result^c) % m. The exponentiation is performed using a simple loop that multiplies the base b or c times, applying the modulus at each step to prevent overflow.

Algorithm

Initialize an empty list goodIndices to store the results.
Iterate through the variables array with index i from 0 to variables.length - 1.
For each variables[i] = [a, b, c, m]:
- Calculate res1 = (a^b) % 10 using a helper function.
  - The helper function computes the power by iterating b times, multiplying by a and taking the modulus 10 at each step.
- Calculate res2 = (res1^c) % m using the same helper function.
  - The helper function computes the power by iterating c times, multiplying by res1 and taking the modulus m at each step.
- If res2 equals target, add i to goodIndices.
Return the goodIndices list.

Walkthrough

We'll create a helper function, let's call it power(base, exp, mod), that calculates (base^exp) % mod. This function initializes a result to 1. It then loops exp times. In each iteration, it multiplies the current result by the base and takes the modulus mod. This repeated application of the modulus prevents the intermediate values from becoming too large and causing an overflow.

The main function will iterate through the variables array. For each i:

Extract a, b, c, and m from variables[i].
Call power(a, b, 10) to compute res1 = (a^b) % 10.
Call power(res1, c, m) to compute res2 = (res1^c) % m.
If res2 is equal to the target, add the index i to a result list.

Finally, return the list of good indices.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> getGoodIndices(int[][] variables, int target) {6        List<Integer> goodIndices = new ArrayList<>();7        for (int i = 0; i < variables.length; i++) {8            int a = variables[i][0];9            int b = variables[i][1];10            int c = variables[i][2];11            int m = variables[i][3];12 13            long res1 = power(a, b, 10);14            long res2 = power(res1, c, m);15 16            if (res2 == target) {17                goodIndices.add(i);18            }19        }20        return goodIndices;21    }22 23    // Helper function for modular exponentiation using simple iteration24    private long power(long base, long exp, long mod) {25        long res = 1;26        for (int i = 0; i < exp; i++) {27            res = (res * base) % mod;28        }29        return res;30    }31}

Complexity

Time

O(N * (max_b + max_c)), where `N` is the length of `variables`, `max_b` is the maximum value of `b_i`, and `max_c` is the maximum value of `c_i`. The helper function `power(base, exp, mod)` takes `O(exp)` time. For each variable set, we call it twice, with exponents `b` and `c`. Given the constraints (`b, c <= 1000`), this is efficient enough to pass.

Space

O(K), where K is the number of good indices found. This is for the output list. The auxiliary space complexity is O(1).

Trade-offs

Pros

Simple to understand and implement.
Correctly handles large numbers by applying the modulus at each step of the multiplication, thus avoiding overflow.

Cons

Less efficient than the exponentiation by squaring method, especially if the exponents were much larger. The time complexity is linear with respect to the exponents.

This approach improves upon the first one by using a more efficient algorithm for modular exponentiation, known as "exponentiation by squaring" or "binary exponentiation". This method significantly reduces the number of multiplications needed to calculate (base^exp) % mod, changing the complexity from linear in exp to logarithmic in exp.

Algorithm

Initialize an empty list goodIndices.
Iterate through the variables array with index i.
For each variables[i] = [a, b, c, m]:
- Calculate res1 = (a^b) % 10 using an efficient modular exponentiation helper function (binary exponentiation).
- Calculate res2 = (res1^c) % m using the same helper function.
- If res2 equals target, add i to goodIndices.
The binary exponentiation algorithm for (base^exp) % mod works as follows:
- Initialize result = 1.
- While exp > 0:
  - If exp is odd, update result = (result * base) % mod.
  - Update base = (base * base) % mod.
  - Update exp = exp / 2.
- Return result.
Return the goodIndices list.

Walkthrough

The core idea is to replace the linear-time power calculation with a logarithmic-time one. The power(base, exp, mod) function is implemented as follows:

It iterates while the exponent exp is greater than 0.
If exp is odd, it means the current power of base is needed in the result, so we multiply the result by the current base (and take the modulus).
In every step, we square the base (and take the modulus) and halve the exp. This works because base^exp = (base^2)^(exp/2) if exp is even, and base^exp = base * base^(exp-1) if exp is odd.

The main logic remains the same as the previous approach:

Iterate through the variables array.
For each [a, b, c, m], calculate res1 = power(a, b, 10).
Then calculate res2 = power(res1, c, m).
If res2 == target, add the index to the result list.

This change in the helper function makes the overall solution much faster.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> getGoodIndices(int[][] variables, int target) {6        List<Integer> goodIndices = new ArrayList<>();7        for (int i = 0; i < variables.length; i++) {8            int a = variables[i][0];9            int b = variables[i][1];10            int c = variables[i][2];11            int m = variables[i][3];12 13            long res1 = power(a, b, 10);14            long res2 = power(res1, c, m);15 16            if (res2 == target) {17                goodIndices.add(i);18            }19        }20        return goodIndices;21    }22 23    // Helper function for modular exponentiation using binary exponentiation24    private long power(long base, long exp, long mod) {25        long res = 1;26        base %= mod;27        while (exp > 0) {28            if (exp % 2 == 1) {29                res = (res * base) % mod;30            }31            base = (base * base) % mod;32            exp /= 2; // or exp >>= 1;33        }34        return res;35    }36}

Complexity

Time

O(N * (log(max_b) + log(max_c))), where `N` is the length of `variables`. The helper function `power(base, exp, mod)` now takes `O(log exp)` time. Since we call it twice for each of the `N` variables, the total time is significantly reduced compared to the linear approach.

Space

O(K), where K is the number of good indices. The auxiliary space complexity is O(1).

Trade-offs

Pros

Highly efficient, with logarithmic time complexity with respect to the exponents.
This is the standard and optimal way to perform modular exponentiation.
Robust and handles very large exponents gracefully.

Cons

The implementation of binary exponentiation is slightly more complex than a simple loop, but it's a standard and highly useful algorithm.

Solutions

Solution

1class Solution {2public3  List<Integer> getGoodIndices(int[][] variables, int target) {4    List<Integer> ans = new ArrayList<>();5    for (int i = 0; i < variables.length; ++i) {6      var e = variables[i];7      int a = e[0], b = e[1], c = e[2], m = e[3];8      if (qpow(qpow(a, b, 10), c, m) == target) {9        ans.add(i);10      }11    }12    return ans;13  }14private15  int qpow(long a, int n, int mod) {16    long ans = 1;17    for (; n > 0; n >>= 1) {18      if ((n & 1) == 1) {19        ans = ans * a % mod;20      }21      a = a * a % mod;22    }23    return (int)ans;24  }25}

1class Solution {2public:3  vector<int> getGoodIndices(vector<vector<int>> &variables, int target) {4    vector<int> ans;5    auto qpow = [&](long long a, int n, int mod) {6      long long ans = 1;7      for (; n; n >>= 1) {8        if (n & 1) {9          ans = ans * a % mod;10        }11        a = a * a % mod;12      }13      return (int)ans;14    };15    for (int i = 0; i < variables.size(); ++i) {16      auto e = variables[i];17      int a = e[0], b = e[1], c = e[2], m = e[3];18      if (qpow(qpow(a, b, 10), c, m) == target) {19        ans.push_back(i);20      }21    }22    return ans;23  }24};

1class Solution:2    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]: return [3        i for i, (a, b, c, m) in enumerate(variables) if pow(pow(a, b, 10), c, m) == target]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem