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.
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
nums = [2,3], k = 3
[2,0,1]
The sections [3] and [2,3] have remainder 0; [2] has remainder 2.
# Example 2
nums = [2,4,3], k = 2
[5,1]
Of the six nonempty contiguous sections, only [3] has an odd product.
Constraints
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
- Reduce each value modulo k as it is read; a product's remainder depends only on its factors' remainders.
- 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.
- 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.
- Add the new counters into the k running totals, since every subarray ending here is a valid choice of removed prefix and suffix.
- 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]
- nums is [2,3] and k is 3. Counters and totals start at [0,0,0].
- Process 2: nothing to extend; the subarray [2] has remainder 2, so counters become [0,0,1] and totals [0,0,1].
- 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].
- 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.