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

"Does it have something to do with negative numbers?" Have you tried using negative numbers with both methods and comparing the answers you get? — Welbog, Jul 12 '17 at 13:59
Oh, now I see. I was inattentive when I was trying to come up with answer on my own, sorry. Thanks a lot :) — ijkl26, Jul 12 '17 at 14:07
No, it was like I wrote last time I've seen this, but It was probably because of that particular problem input constraints. Your version is more general, isn't it? Thanks, I edited question. — ijkl26, Jul 12 '17 at 18:08

score 9 · Accepted Answer · answered Jul 12 '17 at 14:01

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.)

score 3 · Answer 2 · answered Jul 12 '17 at 14:08

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

score 1 · Answer 3 · answered Sep 15 '17 at 12:23

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

Modular arithmetic - competitive programming

3 Answers3