Whats difference bet ((x%c)+c)%c and (x%c)

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.

4 Likes

I didn’t understood hw can it be negative can u pls give an example :upside_down_face:

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:

(1e18*1e18)%MOD

. You will get a negative result. Then, try:

(((1e18*1e18)%MOD)+MOD)%MOD

You will get the proper result.

3 Likes

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.

3 Likes