# LeetCode 523: Continuous Subarray Sum

## Problem Restatement

We are given:

```python
nums
k
```

We need to determine whether there exists a continuous subarray of length at least `2` whose sum is a multiple of `k`.

That means we need some subarray sum satisfying:

$$
subarray\_sum = n \cdot k
$$

for some integer `n`.

Equivalently:

$$
subarray\_sum \bmod k = 0
$$

The official problem asks whether such a subarray exists, with the subarray length required to be at least `2`. ([leetcode.com](https://leetcode.com/problems/continuous-subarray-sum/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums`, integer `k` |
| Output | `True` or `False` |
| Subarray length | At least `2` |
| Goal | Subarray sum is a multiple of `k` |

Function shape:

```python
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        ...
```

## Examples

Example 1:

```python
nums = [23, 2, 4, 6, 7]
k = 6
```

Consider the subarray:

```text
[2, 4]
```

Its sum is:

```text
2 + 4 = 6
```

Since:

```text
6 % 6 = 0
```

the answer is:

```python
True
```

Example 2:

```python
nums = [23, 2, 6, 4, 7]
k = 6
```

The whole array sum is:

```text
23 + 2 + 6 + 4 + 7 = 42
```

Since:

```text
42 % 6 = 0
```

the answer is:

```python
True
```

Example 3:

```python
nums = [23, 2, 6, 4, 7]
k = 13
```

No continuous subarray of length at least `2` has sum divisible by `13`.

So the answer is:

```python
False
```

## First Thought: Check Every Subarray

A direct solution is:

1. Generate every subarray
2. Compute its sum
3. Check divisibility by `k`

There are:

```text
O(n^2)
```

subarrays.

Even with prefix sums, checking all subarrays still costs:

```text
O(n^2)
```

We need something faster.

## Key Insight

Use prefix sums.

Let:

$$
prefix[i] = nums[0] + nums[1] + \cdots + nums[i]
$$

Then the sum of subarray:

```text
(i + 1) to j
```

is:

$$
prefix[j] - prefix[i]
$$

We want this value to be divisible by `k`.

That means:

$$
(prefix[j] - prefix[i]) \bmod k = 0
$$

Rearranging:

$$
prefix[j] \bmod k = prefix[i] \bmod k
$$

This is the crucial observation.

If two prefix sums have the same remainder modulo `k`, then the subarray between them has sum divisible by `k`.

## Example of the Remainder Trick

Suppose:

| Index | Prefix sum | Prefix mod 6 |
|---:|---:|---:|
| 0 | 23 | 5 |
| 1 | 25 | 1 |
| 2 | 29 | 5 |

At indices `0` and `2`, the remainder is the same:

```text
5
```

Subtracting the prefix sums:

```text
29 - 23 = 6
```

which is divisible by `6`.

The corresponding subarray is:

```text
[2, 4]
```

## Important Length Condition

The subarray must have length at least `2`.

If the same remainder appears at indices:

```text
i and j
```

then the subarray length is:

```text
j - i
```

So we require:

```python
j - i >= 2
```

## Algorithm

Maintain:

| Structure | Meaning |
|---|---|
| `prefix_mod` | Current prefix sum modulo `k` |
| `seen` | Maps remainder to earliest index |

Initialize:

```python
seen = {0: -1}
```

This handles subarrays starting at index `0`.

Then scan the array:

1. Update the running prefix remainder
2. If this remainder appeared before:
   - check whether the distance is at least `2`
3. Otherwise, store the current index as the first occurrence

If a valid subarray is found, return `True`.

Otherwise return `False`.

## Correctness

Let the running prefix sum up to index `i` be:

$$
P_i
$$

Suppose two indices `i` and `j` satisfy:

$$
P_i \bmod k = P_j \bmod k
$$

Then:

$$
P_j - P_i
$$

is divisible by `k`.

But:

$$
P_j - P_i
$$

is exactly the sum of the subarray between those positions.

Therefore the corresponding subarray sum is a multiple of `k`.

The algorithm stores the earliest occurrence of each remainder. When the same remainder appears again at a later index, the algorithm checks whether the subarray length is at least `2`.

If such a pair exists, the algorithm returns `True`.

If the algorithm finishes without finding such a pair, then no subarray of length at least `2` has sum divisible by `k`.

Therefore the algorithm is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One pass through the array |
| Space | `O(min(n, k))` | Stores prefix remainders |

## Implementation

```python
from typing import List

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        seen = {0: -1}

        prefix_mod = 0

        for i, num in enumerate(nums):
            prefix_mod = (prefix_mod + num) % k

            if prefix_mod in seen:
                if i - seen[prefix_mod] >= 2:
                    return True
            else:
                seen[prefix_mod] = i

        return False
```

## Code Explanation

Store remainder `0` at index `-1`:

```python
seen = {0: -1}
```

This allows subarrays starting from index `0`.

Track the running prefix remainder:

```python
prefix_mod = 0
```

Update it for each element:

```python
prefix_mod = (prefix_mod + num) % k
```

If this remainder appeared before:

```python
if prefix_mod in seen:
```

then the subarray between the two positions has sum divisible by `k`.

Check the required length:

```python
if i - seen[prefix_mod] >= 2:
    return True
```

If this remainder has never appeared, store its first occurrence:

```python
else:
    seen[prefix_mod] = i
```

We store only the earliest occurrence because it gives the longest possible subarray.

## Testing

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

    assert s.checkSubarraySum([23, 2, 4, 6, 7], 6) is True
    assert s.checkSubarraySum([23, 2, 6, 4, 7], 6) is True
    assert s.checkSubarraySum([23, 2, 6, 4, 7], 13) is False
    assert s.checkSubarraySum([0, 0], 1) is True
    assert s.checkSubarraySum([1, 2, 3], 5) is True
    assert s.checkSubarraySum([1, 0], 2) is False

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Basic divisible subarray |
| Whole array divisible | Large valid subarray |
| No valid subarray | Negative case |
| `[0, 0]` | Zero-sum divisible case |
| `[2, 3]` sum to `5` | Exact multiple |
| Length-1 divisible value | Must reject because length < 2 |