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)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|