We have n numbers, from which we should choose a subset of numbers such that there sum modulo c is 0.

Let's compute cumulative sums of these n numbers and store in array s, hence s[i] = (a[0] + a[1] + .. a[i]).

The first observation is that n >= c and we have only c distinct possible values of remainders upon dividing by c ([0, c-1]). This means that if we consider modulo c values for all n numbers of array s, 2 possibilities are there-

1. There is some s[i] for which s[i]%c = 0.

2. If the above condition does not hold then, we are left with only c - 1 distinct possibilities of remainders and greater than or equal to c numbers (since n >= c). With pigeon-hole analogy, we have c-1 holes and at least c pigeons. So there will be at least one hole with 2 or more pigeons, that is at least one remainder will be repeated.

In the first case, the answer is trivial, just return the first i indexes such that s[i] % c = 0.

For the second case, let's say i, j, (i < j) are the two indexes such that s[i] % c = s[j] % c. Now consider all indexes from i + 1 to j. Sum of all numbers from i + 1 to j is given by s[j] - s[i]. We can see that (s[j] - s[i]) % c = 0.

Whenever a number is divided by c there are only c possible remainders, 0 , 1 , 2 , 3 , .... , c-2 , c-1.

Let array of n numbers be a1, a2, a3 .... an , simply make a cumulative sum array S , S[i] = (a[i] + S[i - 1]) % c.

Given condition n >= c , Now there are n ( >= c) sum elements (S.length) and c possible values so by pigeonhole principle ....

there will be at least a 0 present, in that case answer is all the elements till that index (when cumulative sum is 0).

Or there will be two sum elements Si and Sj such that Si == Sj, in that case answer will be the subarray from i+1 to j (since (Sj - Si + c) % c = 0) .

Hence whenever n >= c answer is always possible else we will have to use dp to calculate it (for which the constraint is too large).