Project Euler 20: Sum of Digits in 100!

In this post I will elaborate a bit on the answer to Project Euler problem 20.  The problem reads

n! means n x (n – 1) x … x 3 x 2 x 1

Find the sum of the digits in the number 100!

100! is a huge number, but with the inclusion of the BigInteger class in .NET 4.0 the problem has been trivialised, just like the solution to Problem 13 and Problem 16.

Without really wanting to comment on the code, because it is very similar to the implementation of Problem 16, it can be implemented in C# as

int sum = 0;
BigInteger fac = 1;

for (int i = 2; i <= 100; i++) {
    fac *= i;
}

while (fac > 0) {
    sum += (int)(fac % 10);
    fac /= 10;
}

Wrapping up

This has been a short post, since there really isn’t anything new to be told in it. I have made the whole  source code available for download.

Other than that I want to make a mention of Dreamshire, which is another blog posting infomation about Project Euler, but the solutions are in perl. The made the solution to Problem 20 as a one-liner.

Posted by Kristian

13 comments

why the code BigInteger always said that “The type or namespace name ‘BigInteger’ could not be found”

The problem is likely that the System.Numerics reference is not added to your project. So first of all you need to use .NET 4 since it was added there. Second you need to add it to your project.

Assuming you use Visual Studio you can add it in the following way.

1. Open your project
2. Right click the References under your solution explorer and choose “Add Reference”
3. Choose the .NET tab
4. Add the System.Numerics reference

That should do the trick.

/Kristian

in the while loop, how exactly is adding the fac to the modulus of 10 and then dividing the fac by 10 working?

Hi Cilaes

We are trying to sum up all the digits in the number ‘fac’ that we just calculated.

Taking the modulo of 10 of a number, means taking the leftover when you divide by 10. In other words you split out the last digit. We then add this last digit to the sum.

After that we make an integer division by 10, meaning that we only keep the integer part of the result. Making an integer division by 10 is the same as removing the last digit.

So in the while loop we add the last digit of fac to the sum and then remove it from fac.

/Kristian

I really think the question is only interesting when you assume the largest unsigned integer is 2^32-1.

wo i had used array to solve this in java nice solution 🙂

BigInteger x = Enumerable.Range(1, 100).Select(i => new BigInteger(i)).Aggregate((total, next) => total * next);
            int[] y = Array.ConvertAll(x.ToString().ToArray(), a => (int)(a-'0'));
            Console.WriteLine(y.Sum());
Chintan Shah

We can reduce the storage space and size of the final value by removing the trailing zeroes during each multiplication.

I mean, after ever multiplication, check if the number is divisible by 10. If yes, divide by 10 before next loop.
Similarly, for input values, use the same check to avoid any trailing zeroes. Tough this is not really necessary for input values since it will anyways be taken care eventually in iterative cycles.

Shikhar Wadhwa

Yes that’s kind of what I did.I divide the factorial by 10^0.2 in each iteration.
That removes all the trailing zeroes(2 zeroes are added for every 110 numbers).But that somehow was not giving the right answer(I mean the right value of factorial for 5,10 etc., which it should) and it was off by little values.I don’t know why that happened.

It seems cheating. There must be a way to calculate factorial sum of digits without requiring more than integer. I can propose some hackish C approach: http://pastebin.com/gt86rxXb

But things are expected to be mathematical, no?
What about prime factorization of factorial or something else like that? I think there must be some enlightening solution.

Madhur Panwar

Hi Kristian
Can you please suggest me some other way with string and integer array to solve this i.e. not to use BigInteger is the constraint.

This is my approach, using strings in C++.

#include

using namespace std;

int nrcif(int x)
{
int n=0;
while(x)
{
x/=10;
n++;
}
return n;
}

void multiply(int v[], int &l, int x)
{
int i, carry = 0, cif;
for(i=l;i>=2;i--)
{
cif=v[i];
v[i]=(cif*x+carry)%10;
carry=(cif*x+carry)/10;
}
v[1]=v[1]*x+carry;
if(v[1]>=10)
{
for(i=l+nrcif(v[1])-1;i>=nrcif(v[1])+1;i--)
v[i]=v[i-nrcif(v[1])+1];
cif=v[1];
for(i=nrcif(v[1]);i>=2;i--)
{
v[i]=v[1]%10;
v[1]/=10;
}
l+=nrcif(cif)-1;
}
}

int main()
{
int v[200],l,i,s=0;
v[1]=1;
l=1;
for(i=1;i<=100;i++)
multiply(v,l,i);
for(i=1;i<=l;i++)
s+=v[i];
cout<<s;
return 0;
}

Jean-Marie Hachey

Leave a Reply