Project Euler 53 solution

project-euler-53.cs

// 2009-06-29
using System;
using System.Collections.Generic;
using System.Text;

namespace ProjectEuler53
{
    class Program
    {
        static void Main(string[] args)
        {
            // count will be the answer of the problem.
            int count = 0;

            for (int n = 1; n <= 100; n++) // upper limit imposed by the problem on 'n' is 100
                for (int r = 1; r <= n; r++) // n > r
                {
                    if (LogCombination(n, r) > 6) // log(1000000) = log(10^6) = 6 log10 = 6
                        count++;
                }

            Console.WriteLine(count);
            Console.ReadKey(true);
        }

        // Memoization dictionary for logarithm of factorials.
        static Dictionary<int, double> dictLogFactorial = new Dictionary<int, double>();

        // Returns logarithm of the combination C(n,r)
        static double LogCombination(int n, int r)
        {
            return LogFactorial(n) - LogFactorial(r) - LogFactorial(n - r);
        }

        /// Returns logarithm of n!, if called before value comes from a dictionary.
        static double LogFactorial(int n)
        {
            if (n == 0 || n == 1)
                return 1;

            if (dictLogFactorial.ContainsKey(n))
                return dictLogFactorial[n];

            double ret = 0;
            for (int i = 1; i <= n; i++)
            {
                ret += Math.Log10(i);
            }
            dictLogFactorial.Add(n, ret);
            return ret;
        }

    }
}