I found this in setter’s solution of problem CHKPTS - Editorial I Ws getting WA for (x%c) but AC fr ((x%c)+c)%c.
When you do (x%c), then the value may become negative, but ((x%c)+c)%c) assures that the value remains positive. It is always a good idea to use this trick when applying MOD.
I didn’t understood hw can it be negative can u pls give an example
It goes negative because of overflow. In certain questions, even when we are asked to compute the answer modulo some M, the current answer might overflow.
Consider a simple scenario where you are asked to compute the product of some large numbers modulo 1e9+7. If the numbers are large(1e18), then simply doing (A * B)%MOD would not be enough as the values would overflow. You can try this on your own compiler. Try multiplying:
. You will get a negative result. Then, try:
You will get the proper result.
consider x= -10 and c=7
then x%c = -10 % 7 = -3
(x%c+c) = (-3 + 7)%7 = 4%7 = 4.
Basically remainder may turn out to be negative but you require it to be positive in Your question . Therefore , you make it positive.