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 <= 100variables[i] == [ai, bi, ci, mi]1 <= ai, bi, ci, mi <= 1030 <= 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
| 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
]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
|
