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 ofgood indices in any order.
Examples
Example 1
|
|
Example 2
|
|
Constraints
1 <= variables.length <= 100
variables[i] == [ai, bi, ci, mi]
1 <= ai, bi, ci, mi <= 10^3
0 <= target <= 10^3
Solution
Method 1 – Modular Exponentiation (Fast Power)
Intuition
We need to compute ((a^b % 10)^c) % m
for each variable. Since the numbers can be large, we use modular exponentiation (fast power) to efficiently compute both steps:
- First, compute
a^b % 10
(since the result cycles every 10, this is fast). - Then, compute
(result)^c % m
using modular exponentiation again.
Approach
- For each variable
[a, b, c, m]
:- Compute
x = pow(a, b, 10)
(modular exponentiation for the last digit). - Compute
y = pow(x, c, m)
(modular exponentiation for the final result). - If
y == target
, add the index to the answer.
- Compute
- Return the list of good indices.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log b + n log c)
, where n is the number of variables. Each pow operation is O(log b) and O(log c). - 🧺 Space complexity:
O(n)
, for the output list.