Welcome to Subscribe On Youtube

2961. Double Modular Exponentiation

Description

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

Solutions

Solution 1: 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)$.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  

• 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;
      }
  };
  

• 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
          ]
  
  

• 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
  }
  

• 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;
  }
  
  

All Problems

All Solutions