# Double Modular Exponentiation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/double-modular-exponentiation)
Canonical: https://scaleengineer.com/dsa/problems/double-modular-exponentiation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays)
---
## 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 <= 100`
* `variables[i] == [ai, bi, ci, mi]`
* `1 <= ai, bi, ci, mi <= 103`
* `0 <= target <= 103`

# Approaches
## 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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Optimized Modular Exponentiation (Exponentiation by Squaring)
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`.
**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).
**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.
### Explanation
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:
1. Iterate through the `variables` array.
2. For each `[a, b, c, m]`, calculate `res1 = power(a, b, 10)`.
3. Then calculate `res2 = power(res1, c, m)`.
4. If `res2 == target`, add the index to the result list.

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

```java
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 binary exponentiation
    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2; // or exp >>= 1;
        }
        return res;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```