Double Modular Exponentiation

MEDIUM

Description

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], (2³ % 10)³ % 10 = 2.
2) For the index 1, variables[1] = [3,3,3,1], (3³ % 10)³ % 1 = 0.
3) For the index 2, variables[2] = [6,1,1,4], (6¹ % 10)¹ % 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], (39³ % 10)¹⁰⁰⁰ % 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

Checkout 2 different approaches to solve Double Modular Exponentiation. Click on different approaches to view the approach and algorithm in detail.

Simple Iterative Modular Exponentiation

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(K), where K is the number of good indices found. This is for the output list. The auxiliary space complexity is O(1).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Double Modular Exponentiation. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Double Modular Exponentiation

Patterns:

Math

Data Structures:

Array

Companies:

Barclays |