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.
