# LeetCode 974: Subarray Sums Divisible by K

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

Return the number of non-empty contiguous subarrays whose sum is divisible by `k`.

A subarray is a continuous part of the array.

The official constraints are:

| Constraint | Value |
|---|---|
| `nums.length` | `1 <= nums.length <= 3 * 10^4` |
| `nums[i]` | `-10^4 <= nums[i] <= 10^4` |
| `k` | `2 <= k <= 10^4` |

Source: LeetCode problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Input | Integer `k` |
| Output | Number of non-empty subarrays with sum divisible by `k` |
| Subarray | Contiguous slice of the array |

Example function shape:

```python
def subarraysDivByK(nums: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [4, 5, 0, -2, -3, 1]
k = 5
```

Output:

```python
7
```

The valid subarrays are:

```python
[4, 5, 0, -2, -3, 1]
[5]
[5, 0]
[5, 0, -2, -3]
[0]
[0, -2, -3]
[-2, -3]
```

Example 2:

```python
nums = [5]
k = 9
```

Output:

```python
0
```

The only subarray is `[5]`, and `5` is not divisible by `9`.

## First Thought: Check Every Subarray

A direct solution is to try every subarray.

For each starting index, extend the ending index and keep a running sum.

```python
answer = 0

for left in range(len(nums)):
    total = 0

    for right in range(left, len(nums)):
        total += nums[right]

        if total % k == 0:
            answer += 1
```

This avoids recomputing each subarray sum from scratch, but it still checks every possible subarray.

There are `O(n^2)` subarrays, which is too slow for `n = 3 * 10^4`.

## Key Insight

Use prefix sums.

Let:

```python
prefix[j] = nums[0] + nums[1] + ... + nums[j]
```

The sum of a subarray from `i + 1` to `j` is:

```python
prefix[j] - prefix[i]
```

This subarray sum is divisible by `k` when:

```python
(prefix[j] - prefix[i]) % k == 0
```

That is equivalent to:

```python
prefix[j] % k == prefix[i] % k
```

So two prefix sums with the same remainder form a subarray whose sum is divisible by `k`.

## Why Remainder Counts Work

Suppose the current prefix sum has remainder `r`.

If we have already seen `r` exactly `count[r]` times, then each previous prefix with remainder `r` forms a valid subarray ending at the current position.

So we add:

```python
count[r]
```

to the answer.

Then we record the current prefix remainder by incrementing:

```python
count[r] += 1
```

We initialize:

```python
count[0] = 1
```

This represents the empty prefix before the array starts.

It lets us count subarrays starting at index `0`.

## Algorithm

1. Create a frequency array or dictionary for remainders.
2. Set `count[0] = 1`.
3. Set `prefix = 0` and `answer = 0`.
4. For each number `x` in `nums`:
   - Update the prefix remainder:

```python
prefix = (prefix + x) % k
```

   - Add previous same-remainder count:

```python
answer += count[prefix]
```

   - Record the current remainder:

```python
count[prefix] += 1
```

5. Return `answer`.

## Negative Numbers

The array may contain negative numbers.

In Python, modulo already returns a nonnegative remainder when `k` is positive.

Example:

```python
-2 % 5 == 3
```

So this line is safe in Python:

```python
prefix = (prefix + x) % k
```

In some languages, `%` can return a negative remainder. In those languages, normalize with:

```python
prefix = ((prefix + x) % k + k) % k
```

## Correctness

We prove that the algorithm counts exactly the subarrays whose sum is divisible by `k`.

For any subarray ending at the current index, its sum can be written as the difference between the current prefix sum and some previous prefix sum.

This subarray sum is divisible by `k` exactly when the current prefix sum and that previous prefix sum have the same remainder modulo `k`.

The algorithm keeps `count[r]`, the number of previous prefix sums with remainder `r`.

When the current prefix remainder is `r`, there are exactly `count[r]` previous prefixes that can pair with it to form a divisible subarray ending at the current index. The algorithm adds exactly this number to the answer.

Then it records the current prefix so future subarrays can use it.

The initial `count[0] = 1` correctly represents the empty prefix, which allows subarrays starting at index `0` to be counted when their prefix sum is divisible by `k`.

Therefore, every valid subarray is counted once, at its ending index, and no invalid subarray is counted.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(k)` | There are only `k` possible remainders |

## Implementation

```python
class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        count = [0] * k
        count[0] = 1

        prefix = 0
        answer = 0

        for x in nums:
            prefix = (prefix + x) % k

            answer += count[prefix]
            count[prefix] += 1

        return answer
```

## Code Explanation

We create one counter for each possible remainder:

```python
count = [0] * k
```

Then initialize the empty prefix:

```python
count[0] = 1
```

The running prefix remainder starts at `0`:

```python
prefix = 0
```

For each number:

```python
prefix = (prefix + x) % k
```

we update the current prefix remainder.

If this remainder appeared before:

```python
answer += count[prefix]
```

then each previous occurrence gives a valid subarray ending here.

Then we record the current prefix remainder:

```python
count[prefix] += 1
```

Finally:

```python
return answer
```

returns the total number of valid subarrays.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.subarraysDivByK([4, 5, 0, -2, -3, 1], 5) == 7
    assert s.subarraysDivByK([5], 9) == 0

    assert s.subarraysDivByK([5], 5) == 1
    assert s.subarraysDivByK([0, 0, 0], 3) == 6
    assert s.subarraysDivByK([-1, 2, 9], 2) == 2
    assert s.subarraysDivByK([1, 2, 3, 4, 5], 3) == 7

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4,5,0,-2,-3,1]`, `k = 5` | Main example with negatives |
| `[5]`, `k = 9` | No valid subarray |
| `[5]`, `k = 5` | Single valid subarray |
| `[0,0,0]` | Every subarray is valid |
| `[-1,2,9]` | Negative number modulo behavior |
| `[1,2,3,4,5]` | Multiple prefix remainder matches |