Why does sum=(sum+n)%n work for negative numbers?

#1

If sum =-2 and n=5 then this should be paired with an element which has modulo 2. but the modulus computed here is (-2+5)%5=3 which is wrong?

#2

hello @mehulbhandari358
see either u pair -2 with element having mod 2 .
or 3 with element having mod 2 .
both are same thing right.

because both will give 0 modulo with 5.
(2+3) mod 5 = (-2 + 2) mod 5
0=0

#3

But in this code we are making a frequency array and only pairing elements which have same mod that’s why we increment pre[sum] in each iteration

#4

oh sorry i misunderstood ur doubt.
see if we are getting same modulo in prefix sum i,e

…a . . . … … . . a…

then that means sum of elements between those two same modulo is divisible by n.
becuase then only
(a+something) %n = a%n
implies something%n=0

so let say we have
…a … a…a…a…
now here if i pick any two a then sum in between them will always be divisible by n.

so if p is the frequency of a in prefix sum array then p*(p-1)/2 such subarray will be there.

#5

Yes I’ve understood that logic but how is this line working in the case of negative numbers: sum=(sum+n)%n, can you please explain with an example …

#6

see that is a one of the modulo property.
image

it is done to avoid negative modulo.