Count Contiguous Segments Whose Sum Is Divisible by K
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the number of nonempty contiguous subarrays of `nums` whose sum is divisible by k. Values may be negative, and a zero sum is divisible by k.
```cpp
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [-1,1,2], k = 2
Output: 3
Explanation: Qualifying intervals contain[-1,1],[2],and[-1,1,2], with sums0,2,and2.
```
**Example 2:**
```text
Input: nums = [0,0,0], k = 3
Output: 6
Explanation: Every one of the three singleton,two length-two,and one length-three intervals has sum0.
```
### Constraints
- The array contains between1 and30000 integers, inclusive.
- Each integer lies in `[-10000,10000]`.
- The divisor k is an integer in the inclusive range `[2,10000]`.
### Contract considerations
The interval must be nonempty and contiguous. No positivity assumption is added to nums.
```hint Read the boundary condition
Equal prefix residues identify exactly the intervals whose sums are multiples of k.
```
### Boundary reminders
The interval must be nonempty and contiguous. No positivity assumption is added to nums.
Overview: Count Contiguous Segments Whose Sum Is Divisible by K. Return the number of nonempty contiguous subarrays of nums whose sum is divisible by k.