Modular arithmetic - competitive programming

Question

I saw a lot of competitive programmers writing code with ((a + b) % d + d) % d in C++. Why don't they just use (a + b) % d? What is that + d inside parentheses good for? Does it have something to do with negative numbers?

Thanks

Answer 1

Yes you are correct. Until C++11 the behaviour of the remainder operator % for negative arguments was left to the implementation, subject to some constraints. And adding d to the left argument can help that so long as the other terms in that argument sum to greater or equal to -d, which, in general is not the case. (-a / d multiples of d for the case of negative a would have been a better additive constant in your particular case.)

Answer 2

Yes, it has something to do with negative numbers. It prevents the result from being a negative number under certain conditions. In this case, when the b variable is negative, the result of b % d is also negative. This result can never be greater than d, so adding d to this result forces the result to be positive.

Below code is Java code, but it has the same principle:

int a = 13;
int b = -23;
int d = 31;

int result1 = (a + b % d + d) % d;
int result2 = (a + b % d) % d;

System.out.println(result1);
System.out.println(result2);

It outputs the following:

21
-10

Answer 3

To avoid integer overflow and to always keep number positive we use modular arithmetic. Compettitve programmers tend to use (a+b)%b instead of a%b when a is a negative number.

a%b = (a+b)%b
(a+b)%b = a%b + b%b = a%b + 0 = a%b

Like a=-2 & b=5 then a%b = 3