DDSA Solutions

3524. Find X Value of Array I

MediumView on LeetCode
ArrayMathDynamic Programming

Problem Overview

Removing a non-overlapping prefix and suffix just leaves one contiguous subarray.

Intuition

Removing a non-overlapping prefix and suffix just leaves one contiguous subarray. The x-value for each remainder is therefore the number of non-empty subarrays whose product is congruent to x modulo k. Track endings with a small DP over residues because k is at most 5.

Algorithm

  1. 1Keep dp[r] as the count of subarrays ending at the previous index with product % k == r.
  2. 2For each num, build next with next[num % k] = 1 for the singleton subarray.
  3. 3For every prior residue r with a positive count, add that count into next[(r * (num % k)) % k].
  4. 4Add every next[r] into ans[r], then swap dp with next.
  5. 5Return ans.

Example Walkthrough

Input: nums = [1,2,3,4,5], k = 3

  1. 1.Singleton [1] contributes to remainder 1.
  2. 2.Extending and starting at later indices fills counts for products mod 3.
  3. 3.Summing over all endings yields the full remainder histogram.

Output: array of k counts

Common Pitfalls

  • •Empty remaining arrays are forbidden; every counted piece is a non-empty subarray.
  • •Multiply with 64-bit intermediates before taking mod k.
  • •Reuse two length-k buffers instead of allocating a new array every step.
  • •Skip zero dp[r] when extending to avoid useless work.
3524.cs
C#
// Approach: Removing a prefix and suffix leaves a contiguous subarray, so
// count subarrays by product % k. dp[r] = number of subarrays ending here
// with product % k == r. At each num, start [num] and extend prior endings
// by multiplying; accumulate into ans.
// Complexity: O(n*k) time, O(k) extra space. Optimal for this DP.
public class Solution
{
    public long[] ResultArray(int[] nums, int k)
    {
        long[] ans = new long[k];
        long[] dp = new long[k];
        long[] next = new long[k];

        foreach (int num in nums)
        {
            Array.Clear(next, 0, k);
            int numMod = num % k;
            next[numMod] = 1;

            for (int r = 0; r < k; r++)
            {
                if (dp[r] == 0)
                    continue;
                next[(int)(1L * r * numMod % k)] += dp[r];
            }

            for (int r = 0; r < k; r++)
                ans[r] += next[r];

            (dp, next) = (next, dp);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems