Get the modulo of a very large number that cannot be stored in any data type in C/C++!

Today we will solve problem of finding modulo of huge numbers.

Lets see the modulo operation first:

It is a distributive over addition, multiplication. i.e.

(A+B)%m = (A%m + B%m) %m

(A*B)%m = (A%m * B%m) %m

These two will help here, mainly the first one.

Consider, 'abcdepqr' is a string of digits, ok?

Is not abcdepqr = (abcde*1000 + pqr) ? Yes, it is.

Similarly, (a*10000000 + bcdepqr), right?

This is the thing we are going to apply.

What will we do is,

Get one variable to store the answer initialized to zero.

Scan the string from left to right,

Everytime multiply the answer by 10 and add the next number and take the modulo and store this as new answer.

E.g. 12345 % 100:

ans = 0

ans = (o*10 + 1)%100

ans = (1*10 + 2)%100

ans = (12*10 + 3)%100

ans = (23*10 + 4)%100

ans = (34*10 + 5)%100

ans = 45.

It means: we, at the end, are doing this only:

a*10000000 + b*1000000 + c*100000 + d*10000 + e*1000 + p*100 + q*10 + r

which is nothing but 'abcdepqr'!

This way have proved the correctness too.

Reference: https://www.hackerearth.com/practice/notes/get-the-modulo-of-a-very-large-number-that-cannot-be-stored-in-any-data-type-in-cc-1/