Project Euler 20: Sum of Digits in 100!

Written by on 5 January 2011

Topics: Project Euler

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.

11 Comments For This Post I'd Love to Hear Yours!

  1. Jie says:

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

  2. Kristian says:

    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

  3. cilaes says:

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

  4. Kristian says:

    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

  5. JW says:

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

  6. swapnil says:

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

  7. Hui says:
    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());
  8. Chintan Shah says:

    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.

  9. Shikhar Wadhwa says:

    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.

  10. Tilir says:

    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.

  11. Madhur Panwar says:

    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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.