Problem

You are given an array of positive integers nums, and a positive integer k.

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

You need to find the x-value of nums, which is the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x when divided by k.

Return an array result of size k where result[x] is the x-value of nums for 0 <= x <= k - 1.

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.

Example 1

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

Input: nums = [1,2,3,4,5], k = 3
Output: [9,2,4]
Explanation:
* For `x = 0`, the possible operations include all possible ways to remove non-overlapping prefix/suffix that do not remove `nums[2] == 3`.
* For `x = 1`, the possible operations are: 
* Remove the empty prefix and the suffix `[2, 3, 4, 5]`. `nums` becomes `[1]`.
* Remove the prefix `[1, 2, 3]` and the suffix `[5]`. `nums` becomes `[4]`.
* For `x = 2`, the possible operations are: 
* Remove the empty prefix and the suffix `[3, 4, 5]`. `nums` becomes `[1, 2]`.
* Remove the prefix `[1]` and the suffix `[3, 4, 5]`. `nums` becomes `[2]`.
* Remove the prefix `[1, 2, 3]` and the empty suffix. `nums` becomes `[4, 5]`.
* Remove the prefix `[1, 2, 3, 4]` and the empty suffix. `nums` becomes `[5]`.

Example 2

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

Input: nums = [1,2,4,8,16,32], k = 4
Output: [18,1,2,0]
Explanation:
* For `x = 0`, the only operations that **do not** result in `x = 0` are: 
* Remove the empty prefix and the suffix `[4, 8, 16, 32]`. `nums` becomes `[1, 2]`.
* Remove the empty prefix and the suffix `[2, 4, 8, 16, 32]`. `nums` becomes `[1]`.
* Remove the prefix `[1]` and the suffix `[4, 8, 16, 32]`. `nums` becomes `[2]`.
* For `x = 1`, the only possible operation is: 
* Remove the empty prefix and the suffix `[2, 4, 8, 16, 32]`. `nums` becomes `[1]`.
* For `x = 2`, the possible operations are: 
* Remove the empty prefix and the suffix `[4, 8, 16, 32]`. `nums` becomes `[1, 2]`.
* Remove the prefix `[1]` and the suffix `[4, 8, 16, 32]`. `nums` becomes `[2]`.
* For `x = 3`, there is no possible way to perform the operation.

Example 3

1
2

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

Examples

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

  1. Compute prefix products modulo k for all positions.
  2. Compute suffix products modulo k for all positions.
  3. 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).
  4. For each remaining subarray, compute its product modulo k and increment the count for that x.
  5. Return the result array.

Code

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

class Solution {
public:
    vector<int> findXValue(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res(k, 0);
        vector<int> pre(n+1, 1), suf(n+2, 1);
        for (int i = 0; i < n; ++i) pre[i+1] = (long long)pre[i] * nums[i] % k;
        for (int i = n-1; i >= 0; --i) suf[i+1] = (long long)suf[i+2] * nums[i] % k;
        for (int l = 0; l < n; ++l) {
            for (int r = 0; r < n-l; ++r) {
                int prod = 1;
                for (int i = l; i < n-r; ++i) prod = (long long)prod * nums[i] % k;
                res[prod]++;
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[] findXValue(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[k];
        for (int l = 0; l < n; ++l) {
            for (int r = 0; r < n-l; ++r) {
                int prod = 1;
                for (int i = l; i < n-r; ++i) prod = (int)((long)prod * nums[i] % k);
                res[prod]++;
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findXValue(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        ans = [0] * k
        for l in range(n):
            for r in range(n-l):
                prod = 1
                for i in range(l, n-r):
                    prod = (prod * nums[i]) % k
                ans[prod] += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n^3), but since k is small and n is up to 1e5, this brute-force is only feasible for small n. For larger n, further optimizations are needed, but for k ≤ 5 and small n, this works.
  • 🧺 Space complexity: O(k), for the result array.