Count Prefix and Suffix Removals by Product Remainder
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given a nonempty array of positive integers `nums` and a positive integer `k`.
Perform one operation by removing a prefix and a suffix, leaving at least one element. The removed prefix and suffix must not overlap, and either or both may be empty.
For every remainder `x` from `0` through `k - 1`, count the operations for which the product of the remaining elements has remainder `x` modulo `k`. Return these counts as an array of length `k`, with the count for remainder `x` at index `x`.
Different removed prefix/suffix lengths are different operations, even if the remaining values happen to be identical.
### C++ Interface
```cpp
class Solution {
public:
vector<long long> resultArray(vector<int>& nums, int k) {
}
};
```
### Examples
**Example 1**
```text
Input: nums = [2,3,5], k = 4
Output: [0,1,3,2]
```
The six possible nonempty remaining arrays have these products and remainders:
| Remaining positions | Product | Remainder modulo 4 |
| --- | --- | --- |
| `[0,0]` | 2 | 2 |
| `[1,1]` | 3 | 3 |
| `[2,2]` | 5 | 1 |
| `[0,1]` | 6 | 2 |
| `[1,2]` | 15 | 3 |
| `[0,2]` | 30 | 2 |
The counts for remainders `0,1,2,3` are `0,1,3,2`.
**Example 2**
```text
Input: nums = [7,7], k = 1
Output: [3]
```
Keeping the first element, keeping the second element, or keeping both gives three different operations. Every product has remainder zero modulo one. Keeping both corresponds to removing an empty prefix and an empty suffix.
### Constraints
- `1 <= nums.length <= 100000`.
- `1 <= nums[i] <= 1000000000`.
- `1 <= k <= 5`.
### Clarifying Questions
- Can the remaining array be empty? No.
- Does removing neither end count? Yes. Both removed pieces may be empty.
- Are removal operations repeated on an already shortened array? No. Count ways to perform the single operation on the original array.
- Can different positions with equal values count separately? Yes. Their prefix/suffix choices differ.
### What a Strong Answer Covers
- Non-overlapping removals, their possible emptiness, and a nonempty remaining array.
- Correct counts for every remainder, with distinct position choices counted separately.
- Large products and counts, single-element inputs, and `k = 1`.
- Resource bounds for `100000` elements and the full allowed modulus range.
### Follow-up Questions
- When `k = 1`, which output entries exist and which operations do they count?
- Why do the two identical singleton remnants in the second example represent different operations?
```hint Count by the right endpoint
Each operation leaves a unique nonempty contiguous subarray. Track product-remainder counts for subarrays ending at the current position: start a new singleton or extend a subarray ending at the previous position.
```
Overview: Count ways to remove a prefix and suffix while leaving a nonempty array, grouped by the remaining product remainder. Include empty removed pieces and distinguish equal values at different positions.