How to find modulo of a sum of numbers?

Question

I am seeking for a way to find modulo of a sequence of numbers like: (a1 + a2 + a3 + a4 + ... + an) mod x

Is there any way/property of modulo function so that I can compute mod of this sequence from the individual mods of numbers in sequence.

You know that (a + b) % x == ((a%x) + (b%x)) % x, right? – Oliver Charlesworth Oct 12 '14 at 08:30 — Oliver Charlesworth, Oct 12 '14 at 08:30
I have the exact same question. Have you found your answer? – Thariq Nugrohotomo Nov 16 '16 at 12:14 — Thariq Nugrohotomo, Nov 16 '16 at 12:14

hasan · Answer 1 · 2018-01-29T07:57:23.343

As I can recall. you can:

(a1 mod x + a2 mod x + a3 mod x + ... + an mod x) mod x

Such equation will benefit one purpose. if the sum of the numbers exceeds the capacity of the variable used for summation. ex. 32 bit int.

This way it is most probably the sum of modulars will fit in the used var for summation. depending on x value and sequence length.

Sample Code

int sum = 0;
for (int i=0;i<n;i++)
   sum += a[i] % x;
int mod = sum % x;

Better Approach (not very sure)

int sum = 0;
for (int i=0;i<n;i++) {
   sum += a[i] % x;
   sum %= x;
}
int mod = sum;

score 11 · Answer 2 · edited Oct 12 '14 at 09:23

11

Mod operator is distributive;

( x + y ) % z

... is equivalent to:

( x % z + y % z ) % z

edited Oct 12 '14 at 09:23

Unihedron

answered Oct 12 '14 at 08:34

ravi

score 1 · Answer 3 · answered Oct 02 '21 at 11:36

As the purpose of doing this is usually to avoid overflows, the below might still overflow as we are summing all mod values.

Wrong approach if we want to avoid overflows :

(a1 mod x + a2 mod x + a3 mod x + ... + an mod x) mod x

We need to mod after each and every sum.

Assuming ai < x,

((((a1 + a2) mod x) + a3) mod x) + a4) mod x ....

should avoid the overflows.

3 Answers3