How to take modulus of a large value stored in array?

Question

Suppose I have a integer array containing digits and I want to take modulus of value stored 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 into a number like 987654321987654321987654321987654321.

In C language long long int permits only 10^18. I want to take modulus with 10^9+7. How can i do that?

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 is too much for a typical long long, you need to perform your modulus 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 the way you convert an array of digits to a number - your code used pow, and treated digits at higher indexes as higher-order digits. This creates precision problems once you get past the highest power of ten that can be represented as double.
• Moved the %= into the loop - your code does not let the number overflow by keeping the value in the range from 0 to 1000000006, inclusive.

Running this code produces the same value that you would obtain with a library that supports arbitrary precision of integers (I used Java BigInteger here).