For above solution I don’t understand why we do M[0] = 1 initially?
This is because initial sum is 0 and we need to add initial sum to the count.
1 Like
Yes, thank you!
And why do we do this: M[(psums % N + N) % N]++?
Can you explain me the math behind this equation, how does this single line consider the sum of, for example, the 4th, 5th and 6th elements in an array with 10 elements?
And why do we do M[0] = 1, knowing that just a few lines after we will set M[0] to the exact same thing?
Thank you very much!
Hi,
psums is the current prefix sum and it is possible psums could be negative. This leads to some errors in modulus operations in some languages like C++ e.g -6 % 5 = -1 in c++(i.e subtract -1 from -6 to get -5 which is a multiple of 5. Its not wrong but answer is negative), but we actually want it to equal 4(i.e subtract 4 from -6 to get -10 which is a multiple of 5) . To fix this, you first mod psums by N to make it smaller than N, then add N(this has no effect on the answer) to make it positive. The reason why we mod by N again is for the case when the new value is larger than N(when psums is positive).
That line just keeps track of the prefix sums of the array, the real work is done in the x*(x-1)/2 part. For a subarray to be counted, the sum must be divisible by n. This means the prefix sum%N till the end of the subarray must equal the prefix sum%N before the start of the array so that when you subtract them it equals 0. This reduces the problem to count all pairs of equal prefix sums %N which x*(x-1)/2 does.
We do not set M[0] = 1 again. Psums starts from 1st element and ends at the sum of all elements therefore it does not count initial case.
1 Like
Thank you so much!