PROJECT EULER #20

Link to page

n! means n x (n - 1) x ... x 3 x 2 x 1

Find the sum of the digits in the number 100!

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main(string[] args)
       {
           //Problem 20
           DateTime start = DateTime.Now;
           int carry = 0, sum =0;
           List<int> factorial100 = new List<int>() {100};
           List<int> temp = new List<int>();
           for(int i=99;i>1;i--)
           {
               //multiply each 'digit' (base million) with present multiplier (i)
               //and add carry from previous calculation
               //divide by 1000000 to get carry and new 'digit' (nice method DivRem gives both)
               foreach (int j in factorial100)
               {
                   int digitInBaseMillion;
                   int k = j*i + carry;
                   carry = Math.DivRem(k, 1000000,out digitInBaseMillion);
                   temp.Add(digitInBaseMillion);
               }
               if (temp.Count==factorial100.Count && carry != 0)
                   temp.Add(carry);
               carry = 0;
               factorial100.Clear();
               foreach(int j in temp)
                   factorial100.Add(j);
               temp.Clear();
           }
           foreach (int j in factorial100)
           {
               char[] c = j.ToString().ToCharArray();
               for (int i = 0; i < c.Length; i++)
                   sum += Convert.ToInt32(c[i].ToString());
           }
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("{0}\nThis took {1}", sum, time);
           Console.ReadKey();
       }
   }
}