Create a gist now

Instantly share code, notes, and snippets.

@krk /project-euler-53.cs Secret
Created Jun 27, 2017

What would you like to do?
Project Euler 53 solution
// 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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment