Skip to content

3524. Find X Value of Array I

SourceWeekly Contest 446 Q3DifficultyMediumRating2008

Description

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:

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:

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:

Input: nums = [1,1,2,1,1], k = 2

Output: [9,6]

 

Constraints:

  • 1 <= nums[i] <= 109
  • 1 <= nums.length <= 105
  • 1 <= k <= 5

Solutions

Solution 1: Dynamic Programming

Thinking

Removing a prefix and a suffix leaves one subarray; we need how many have product \(\equiv x \pmod k\). \(n \le 10^5\) and \(k \le 5\), so DP on remainders replaces enumeration.

Let \(f[i][r]\) be the number of subarrays ending at \(i\) whose product is \(r\) modulo \(k\). Transfer from \(f[i-1]\) by multiplying \(nums[i]\), and start a new subarray at \(i\). Summing by remainder fills \(\textit{result}\).

After removing any non-overlapping prefix and suffix, the remainder is a non-empty subarray. The task is to count subarrays whose product modulo \(k\) equals \(0, 1, \ldots, k-1\).

Let \(f[r]\) be the number of subarrays ending at the current index whose product is \(r\) modulo \(k\). Scan \(x = \textit{nums}[i]\) from left to right and use \(g\) for the new ending-at-\(i\) state: move each \(f[r]\) to \(g[(r \times x) \bmod k]\), then add the singleton subarray \([x]\) into \(g[x \bmod k]\). Add \(g\) into the answer and set \(f \leftarrow g\).

The time complexity is \(O(n \times k)\) and the space complexity is \(O(k)\), where \(n\) is the length of \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def resultArray(self, nums: list[int], k: int) -> list[int]:
        ans = [0] * k
        f = [0] * k
        for x in nums:
            g = [0] * k
            for r, cnt in enumerate(f):
                g[r * x % k] += cnt
            g[x % k] += 1
            for r, cnt in enumerate(g):
                ans[r] += cnt
            f = g
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public long[] resultArray(int[] nums, int k) {
        long[] ans = new long[k];
        long[] f = new long[k];
        for (int x : nums) {
            long[] g = new long[k];
            for (int r = 0; r < k; ++r) {
                g[(int) (1L * r * x % k)] += f[r];
            }
            g[x % k] += 1;
            for (int r = 0; r < k; ++r) {
                ans[r] += g[r];
            }
            f = g;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        vector<long long> ans(k);
        vector<long long> f(k);
        for (int x : nums) {
            vector<long long> g(k);
            for (int r = 0; r < k; ++r) {
                g[1LL * r * x % k] += f[r];
            }
            g[x % k] += 1;
            for (int r = 0; r < k; ++r) {
                ans[r] += g[r];
            }
            f.swap(g);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func resultArray(nums []int, k int) []int64 {
    ans := make([]int64, k)
    f := make([]int64, k)
    for _, x := range nums {
        g := make([]int64, k)
        for r, cnt := range f {
            g[r*x%k] += cnt
        }
        g[x%k]++
        for r, cnt := range g {
            ans[r] += cnt
        }
        f = g
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function resultArray(nums: number[], k: number): number[] {
    const ans = Array(k).fill(0);
    let f = Array(k).fill(0);
    for (const x of nums) {
        const g = Array(k).fill(0);
        for (let r = 0; r < k; ++r) {
            g[(r * x) % k] += f[r];
        }
        g[x % k] += 1;
        for (let r = 0; r < k; ++r) {
            ans[r] += g[r];
        }
        f = g;
    }
    return ans;
}

Comments