An interesting easy problem

I haven’t been writing for a pretty long time now Anyways.

Someone asked me to solve this problem:

Given an array A of integers of length N, find a sub-array whose sum is a multiple of N.

To solve it in a brute force manner could be a reasonable exercise for beginners in programming. The solution is to just consider all possible sub-arrays and check if their sum is a multiple of N. This could be O(N³). If you use an cumulative sums array (ie, S[i] =∑A[k] where k goes from 1 to i) the solution is slightly smarter and can be solved in O(N²): just choose all possible (a,b) such that 1<=a<b<=N and see if S[b]-S[a] is a multiple of N (make sure you handle corner cases).

Now we come to the more interesting linear solution. Use the same cumulative sums array as above but make it so that S[i] = ((∑A[k]) mod N) or in C parlance: S[i] = (∑A[k])%N. Clearly, if any of these values is 0, we are done: the array A[1], A[2], …, A[i] constitutes a sub-array with the required property if S[i] = 0. Also, the notice that if any of the remainders occur twice, i.e. S[i] = S[j] for i < j, then A[i+1], A[i+2], …, A[j] constitutes a subarray with the required property. With these observations the linear solution should be obvious: just use another array of size N to keep track of which remainder was seen where (i.e. let R[i] be the index in the array S, where the remainder was i) and then output a solution when a particular remainder is seen twice, or when the remainder 0 is seen.

Some of you may also have stumbled onto another realization:

A solution to this problem always exists!

Its not such a big deal anyway: If none of the remainders occur twice in the cumulative sums array, clearly one of the remainders has to be 0 (since there are N cumulative sums and N remainders)! Thus, the result!