Skip to content

Practice Find X Value of Array I

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3524
LeetCode Problem

Find X Value of Array I

Problem Statement

Remove a prefix and a suffix from nums, leaving a nonempty contiguous section. Either removed part may be empty. For each remainder x from 0 through k - 1, count the choices whose remaining product modulo k equals x. Return those counts in remainder order. Different positions count separately even when their values match. Approach: Keep k counters for products of subarrays ending at the previous position. For each new value, extend every counter using (remainder * value) % k and add its one-element subarray. Accumulate these counters into the result. This avoids constructing enormous products and takes O(nk) time and O(k) extra space. Use 64-bit counts.

Source: Find X Value of Array I on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [2,3], k = 3
Output
[2,0,1]
Explanation

The sections [3] and [2,3] have remainder 0; [2] has remainder 2.

# Example 2

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

Of the six nonempty contiguous sections, only [3] has an odd product.

Constraints

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000000
1 <= k <= 5

How to solve Find X Value of Array I

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

The remaining section is a nonempty contiguous subarray, and with k at most 5 you can keep one count per possible product remainder for the subarrays ending at the current index; extending each by one element maps remainders to remainders without forming real products.

Why brute force is not enough

Enumerating all n(n + 1) / 2 subarrays and multiplying their elements is O(n^2) or worse, about 5 times 10^9 subarrays for n up to 100,000, and products of values up to 10^9 overflow at once.

Approach

  1. Reduce each value modulo k as it is read; a product's remainder depends only on its factors' remainders.
  2. Keep k counters where counter r is the number of subarrays ending at the previous index with product remainder r; together they describe exactly those subarrays.
  3. For the current value v, build fresh counters: each old counter r moves to (r times v) mod k, and the single-element subarray adds one at v mod k. Build separately rather than in place.
  4. Add the new counters into the k running totals, since every subarray ending here is a valid choice of removed prefix and suffix.
  5. After the last element the totals are the answer in remainder order; use 64-bit counts.

Walkthrough of Example 1

nums = [2,3], k = 3 → [2,0,1]

  1. nums is [2,3] and k is 3. Counters and totals start at [0,0,0].
  2. Process 2: nothing to extend; the subarray [2] has remainder 2, so counters become [0,0,1] and totals [0,0,1].
  3. Process 3 (remainder 0): extending [2] gives (2 times 0) mod 3 = 0 and the subarray [3] has remainder 0, so counters become [2,0,0].
  4. Totals become [2,0,1], the expected output: [3] and [2,3] have remainder 0 and [2] has remainder 2.

Time and space

Time O(n k) · Space O(k). n is the array length and k the modulus, at most 5; each element touches k counters and only two counter arrays of size k plus the answer are kept.

Interview pitfalls

  • Multiplying raw values instead of remainders; two raw values overflow 64 bits.
  • Updating counters in place so a freshly produced remainder is multiplied again in the same step.
  • Storing counts in 32-bit integers; totals approach 5 times 10^9.
  • Collapsing equal values into one choice; positions count separately.
  • Mishandling k equal to 1, where the single answer entry must be n(n + 1) / 2.

Follow-up questions interviewers ask

  • How would you answer queries fixing the right endpoint and asking for a given remainder count?
  • If k were up to 10^5, which structure replaces the k counters?
  • What does the recurrence become for sums instead of products?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to Find X Value of Array I.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.