Find X Value of Array II
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, determine the x-value of nums for xi after performing the following actions:
- Update
nums[indexi]tovaluei. Only this step persists for the rest of the queries. - Remove the prefix
nums[0..(starti - 1)], wherenums[0..(-1)]represents the empty prefix.
Return an array result of size queries.length where result[i] is the answer for the i^th 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.
nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]][2,2,2]nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]][1,0]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