Scale Engineer

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] = [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 <= 100
  • variables[i] == [ai, bi, ci, mi]
  • 1 <= ai, bi, ci, mi <= 103
  • 0 <= target <= 103

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:

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

Finally, return the list of good indices.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> getGoodIndices(int[][] variables, int target) {        List<Integer> goodIndices = new ArrayList<>();        for (int i = 0; i < variables.length; i++) {            int a = variables[i][0];            int b = variables[i][1];            int c = variables[i][2];            int m = variables[i][3];             long res1 = power(a, b, 10);            long res2 = power(res1, c, m);             if (res2 == target) {                goodIndices.add(i);            }        }        return goodIndices;    }     // Helper function for modular exponentiation using simple iteration    private long power(long base, long exp, long mod) {        long res = 1;        for (int i = 0; i < exp; i++) {            res = (res * base) % mod;        }        return res;    }}

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.

Solutions

class Solution {public  List<Integer> getGoodIndices(int[][] variables, int target) {    List<Integer> ans = new ArrayList<>();    for (int i = 0; i < variables.length; ++i) {      var 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.add(i);      }    }    return ans;  }private  int qpow(long a, int n, int mod) {    long ans = 1;    for (; n > 0; n >>= 1) {      if ((n & 1) == 1) {        ans = ans * a % mod;      }      a = a * a % mod;    }    return (int)ans;  }}

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 →

Next problem