Input: nums = [1,1,2,1,1], k = 2
Output: [9,6]

Constraints

1 <= nums[i] <= 10^9
1 <= nums.length <= 10^5
1 <= k <= 5

Solution

Method 1 – Prefix/Suffix Product Modulo Counting

Intuition

Since k is small (≤5), we can precompute prefix and suffix products modulo k. For each possible subarray (after removing a prefix and a suffix), we count the number of ways the product modulo k is x for each x in 0..k-1.

Approach

Compute prefix products modulo k for all positions.
Compute suffix products modulo k for all positions.
For each possible subarray (from i to j), the product is:
- prefix_prod[i-1]^{-1} * suffix_prod[j+1]^{-1} * total_prod (all mod k)
- But since k is small, we can brute-force all possible (l, r) pairs (remove prefix of length l and suffix of length r, with l + r < n).
For each remaining subarray, compute its product modulo k and increment the count for that x.
Return the result array.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> findXValue(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> res(k, 0);\n        vector<int> pre(n+1, 1), suf(n+2, 1);\n        for (int i = 0; i < n; ++i) pre[i+1] = (long long)pre[i] * nums[i] % k;\n        for (int i = n-1; i >= 0; --i) suf[i+1] = (long long)suf[i+2] * nums[i] % k;\n        for (int l = 0; l < n; ++l) {\n

Related Tags