PROJECT EULER #53

Link to Project Euler problem 53

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ⁵C₃ = 10.

In general,

nCr =

n! ______ r!(n-r)!

,where r <= n, n! = n*(n-1)*...*3*2*1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of ⁿC_r, for 1 <= n <= 100, are greater than one-million

My first effort, using the BigInt class, used 25 seconds so I found a much better way using Pascal's Triangle (of course):

effort #1:

using System;

namespace ProjectEuler
{
 class Program
 {
     static void Main()
     {
         //Problem 53
         DateTime start = DateTime.Now;
         int count = 0;
         for (int i = 22; i < 101; i++)
         {
             BigInt n = FactorialBigInt(i);
             for (int j = i; j > 0; j--)
             {
                 BigInt r = FactorialBigInt(j);
                 BigInt s = FactorialBigInt(i - j);
                 BigInt result = n / (r * s);
                 count += result > 1000000 ? 1 : 0;
             }
         }
         Console.WriteLine(count);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
     public static BigInt FactorialBigInt(int n)
     {
         n = n == 0 ? 1 : n;
         BigInt factorial = 1;
         for (int i = 1; i <= n; i++)
         {
             factorial *= i;
         }
         return factorial;
     }
 }
}

effort #2:

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
 class Program
 {
     static void Main()
     {
         //Problem 53
         DateTime start = DateTime.Now;
         int count = 0;
         List<int[]> pascT = new List<int[]>();
         for (int i = 0; i < 101; i++)
         {
             int[] line=new int[i+1];
             pascT.Add(line);
         }
         pascT[0][0] = 1;
         for (int i = 1; i < pascT.Count; i++)
             for (int j = 0; j <= i; j++)
                 if (j == 0  j == i)
                     pascT[i][j] = 1;
                 else if (pascT[i - 1][j] + pascT[i - 1][j - 1] >= 1000000)
                 {
                     pascT[i][j] = 1000000;
                     count++;
                 }
                 else
                     pascT[i][j] = pascT[i - 1][j] + pascT[i - 1][j - 1];
         Console.WriteLine(count);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
 }
}