2961

2961. Double Modular Exponentiation (Medium)

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

Solution 1. Fast Pow

// OJ: https://leetcode.com/problems/double-modular-exponentiation
// Author: github.com/lzl124631x
// Time: O(N * (logM)^2) where `N` is the length of `A`, and `M` is the maximum elements in `A[i]`
// Space: O(1) extra space
class Solution {
    long pow(long base, long exp, long mod) {
        long ans = 1;
        while (exp) {
            if (exp & 1) ans = ans * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return ans;
    }
public:
    vector<int> getGoodIndices(vector<vector<int>>& A, int target) {
        vector<int> ans;
        for (int i = 0; i < A.size(); ++i) {
            int a = A[i][0], b = A[i][1], c = A[i][2], m = A[i][3];
            if (pow(pow(a, b, 10), c, m) == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

Discussion

https://leetcode.com/problems/double-modular-exponentiation/solutions/4384476/c-fast-pow/