Problem

You are given an array of positive integers nums and a positive integer k. You are also given a 2D array queries, where queries[i] = [indexi, valuei, starti, xi].

You are allowed to perform an operation once on nums, where you can remove any suffix from nums such that nums remains non-empty.

The x-value of nums for a given x is defined as the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x modulo k.

For each query in queries you need to determine the x-value of nums for xi after performing the following actions:

  • Update nums[indexi] to valuei. Only this step persists for the rest of the queries.
  • Remove the prefix nums[0..(starti - 1)] (where nums[0..(-1)] will be used to represent the empty prefix).

Return an array result of size queries.length where result[i] is the answer for the ith query.

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray that starts at any point within the array and extends to the end of the array.

Note that the prefix and suffix to be chosen for the operation can be empty.

Note that x-value has a different definition in this version.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: nums = [1,2,3,4,5], k = 3, queries =
[[2,2,0,2],[3,3,3,0],[0,1,0,1]]
Output: [2,2,2]
Explanation:
* For query 0, `nums` becomes `[1, 2, 2, 4, 5]`, and the empty prefix **must** be removed. The possible operations are: 
* Remove the suffix `[2, 4, 5]`. `nums` becomes `[1, 2]`.
* Remove the empty suffix. `nums` becomes `[1, 2, 2, 4, 5]` with a product 80, which gives remainder 2 when divided by 3.
* For query 1, `nums` becomes `[1, 2, 2, 3, 5]`, and the prefix `[1, 2, 2]` **must** be removed. The possible operations are: 
* Remove the empty suffix. `nums` becomes `[3, 5]`.
* Remove the suffix `[5]`. `nums` becomes `[3]`.
* For query 2, `nums` becomes `[1, 2, 2, 3, 5]`, and the empty prefix **must** be removed. The possible operations are: 
* Remove the suffix `[2, 2, 3, 5]`. `nums` becomes `[1]`.
* Remove the suffix `[3, 5]`. `nums` becomes `[1, 2, 2]`.

Example 2

1
2
3
4
5
6

Input: nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]
Output: [1,0]
Explanation:
* For query 0, `nums` becomes `[2, 2, 4, 8, 16, 32]`. The only possible operation is: 
* Remove the suffix `[2, 4, 8, 16, 32]`.
* For query 1, `nums` becomes `[2, 2, 4, 8, 16, 32]`. There is no possible way to perform the operation.

Example 3

1
2

Input: nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]
Output: [5]

Constraints

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5
  • 1 <= queries.length <= 2 * 10^4
  • queries[i] == [indexi, valuei, starti, xi]
  • 0 <= indexi <= nums.length - 1
  • 1 <= valuei <= 10^9
  • 0 <= starti <= nums.length - 1
  • 0 <= xi <= k - 1

Examples

Solution

Method 1 – Prefix Product Modulo Counting (Brute-force for Small k)

Intuition

Since k is small (≤5), for each query, we can update the array, then for the required prefix, count the number of suffixes such that the product of the remaining subarray modulo k equals xi.

Approach

  1. For each query:
    • Update nums[indexi] to valuei.
    • For the subarray nums[starti:]:
      • For each possible suffix (from starti to n-1), compute the product modulo k.
      • For each possible subarray nums[starti:j+1], compute the product and count if it matches xi.
    • Store the count for this query.
  2. Return the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> findXValue(vector<int>& nums, int k, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> res;
        for (auto& q : queries) {
            int idx = q[0], val = q[1], start = q[2], x = q[3];
            int old = nums[idx];
            nums[idx] = val;
            int cnt = 0;
            for (int l = start; l < n; ++l) {
                int prod = 1;
                for (int r = start; r <= l; ++r) prod = (long long)prod * nums[r] % k;
                if (prod == x) cnt++;
            }
            res.push_back(cnt);
            // nums[idx] = old; // No need to revert as update is persistent
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findXValue(self, nums: list[int], k: int, queries: list[list[int]]) -> list[int]:
        n = len(nums)
        ans = []
        for idx, val, start, x in queries:
            nums[idx] = val
            cnt = 0
            for l in range(start, n):
                prod = 1
                for r in range(start, l+1):
                    prod = (prod * nums[r]) % k
                if prod == x:
                    cnt += 1
            ans.append(cnt)
        return ans

Complexity

  • ⏰ Time complexity: O(Q * n^2), where Q is the number of queries and n is the array length. This is only feasible for small n and k. For large n, further optimizations (like segment trees or prefix product caching) are needed.
  • 🧺 Space complexity: O(1) (excluding output), as we only use a few counters.