### PROBLEM LINK:

**Author:** Yash Sangai

**Tester:** Sudhanshu Gupta

**Editorialist:** Sudhanshu Gupta

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Pigeonhole principle, DP

### PROBLEM:

In a given array of integers of size N, find the smallest sub-array whose sum is divisible by N.

### EXPLANATION:

Claim:

There is always such a subset. Moreover, there is always a consecutive subsegment of any sequence of numbers that corresponds to the multiset’s elements with the sum divisible by the multiset’s size.

Proof:

Let’s denote a1 + a2 + … + ak by bk. So, we obtain:

```
b0 = 0
b1 = a1
b2 = a1 + a2
...
bN = a1 + a2 + ... + aN
```

It is easy to see that aL + aL+1 + … + aR (L <= R) equals to bR - bL-1. Therefore, if there are two values with equal residues modulo N among b0, b1, …, bN then we take the first one for L-1 and the second one for R and the required subsegment is found.

There are N+1 values of bi and N possible residues for N. So, according to the pigeonhole principle the required subsegment will always exist.

Some implementation details:

While calculating the value of bi you should use that bi equals to bi-1 + ai, that allows you to precompute all bs in O(N) time. Practically, only bi modulo N are important. Then you can just sort the numbers along with their indices in order to find the duplicates among the residues.

### SOLUTIONS:

Solution can be found here.