Solution of nMultiple

Consider the array of partial sums s_i = (a₁ + a₂ + … + a_i) % N, (1 ≤ i ≤ N). Clearly, this array contains exactly N values between 0 and N-1.

If there exists an index i such that s_i = 0, then we can construct our subset by choosing all elements a_j (1 ≤ j ≤ i). Otherwise, it follows from Dirichlet's principle that at least one value occurs multiple times. Denote by i and j two indices such that i < j, s_i = s_j. Then we can construct our subset by choosing all elements a_k (i < k ≤ j).

Note that this solution proves another property of the problem: besides the fact that any array of size N contains at least one subset whose sum is divisible by N, it also contains at least one such subset that is also a continuous subsequence of the array.