Project Euler problem 16(Sum of digits of 2^1000)


This program calculates the sum of digits of 2^1000.

Since there is no datatype large enough to hold such a large number in C, we have to use arrays to get around this limitation. First, declare an array that is large enough to hold the number of digits that the resulting value will have. Next, we define our multiplication function (void multiply). This function basically performs multiplication as is done manually using pen and paper.

Thus the number is calculated. We use one index to store one digit of the number.

 

#include<conio.h>
#include<stdio.h>
void multiply(int *digits, int multiplier)
{
int carry=0;
for(int i=0;i<400;i++)
{
int dig=digits[i];
dig*=multiplier;
dig+=carry;
digits[i]=dig%10;
carry=dig/10;
}
}
int main()
{
int digits[400],n=1000,i,numsum=0;
for(i=0;i<400;i++)
{
digits[i]=0;
}
digits[0]=1;
for(i=1;i<=n;i++)
{
multiply(digits,2);
}
for(i=0;i<400;i++)
{
numsum+=digits[i];
}
printf("%d",numsum);
getch();
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s