How to take a module of large value stored in an array?

Question

Suppose I have an integer array containing numbers, and I want to store the value module in it, i.e.

int a[36]={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9} 

and convert it to a number like 987654321987654321987654321987654321 .

In C long long int only 10 ^ 18 is allowed. I want to take a module with 10 ^ 9 + 7. How can I do this?

Program:

 int main() { int a[36]={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9}; long long int temp=0; int i; for(i=0;i<36;i++) { temp=temp+a[i]*pow(10,i); } temp=temp%1000000007; printf("%lld",temp); return 0; } 

Answer 1

Since 36 decimal digits are too large for a typical long long , you need to perform a module operation during the conversion:

 int a[36]={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9}; long long int temp=0; for(int i=35 ; i >= 0 ; i--) { temp = 10*temp + a[i]; temp %= 1000000007; } printf("%lld",temp); 

I made two changes to your code:

• Fixed how you converted an array of numbers to numbers - your code used pow and processed numbers with higher indices as higher order numbers. This creates problems with accuracy if you pass the highest power of ten, which can be represented as double .
• Moved %= to loop - your code does not allow overflow of the number, storing the value in the range from 0 to 1000000006 inclusive.

Running this code produces the same value that you get with a library that supports arbitrary integer precision (I used Java BigInteger here ).