patterncsharpModerate
Solving Project Euler Problem 1 using extension methods
Viewed 0 times
problemsolvingextensionmethodsprojectusingeuler
Problem
As a self taught developer I never did any of the Project Euler problems, so I decided to just start with Problem 1 which states
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
The first step had been to create an extension method which takes a
which can be called for instance like so
I am not 100% sure about the name of that method but couldn't come up with an alternative name so for sure I would like to hear suggestions for that.
The meat about solving the problem
To solve the actual problem one would call it like
Any suggestions about the shown code are welcome.
Because math has closed its doors for me after finishing school, I don't know if there is any math trick to do this any faster or easier.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
The first step had been to create an extension method which takes a
lowerLimit and an upperLimit returning an IEnumerablepublic static IEnumerable GetSequence(this int lowerLimit, int upperLimit)
{
if (upperLimit < lowerLimit) { throw new ArgumentOutOfRangeException("lowerLimit needs to be less or equal to upperLimit"); }
for (int i = lowerLimit; i < upperLimit; i++)
{
yield return i;
}
}which can be called for instance like so
int lowerLimit = 1;
var sequence = lowerLimit.GetSequence(1000);I am not 100% sure about the name of that method but couldn't come up with an alternative name so for sure I would like to hear suggestions for that.
The meat about solving the problem
public static class SolverOfProblemOne
{
public static int Solve(this int lowerLimit, int upperLimit, params int[] multiples)
{
if (upperLimit i.IsMultipleOf(multiples))
.Sum();
}
private static bool IsMultipleOf(this int value, IEnumerable multiples)
{
foreach (int multiple in multiples)
{
if (value % multiple == 0) { return true; }
}
return false;
}
}To solve the actual problem one would call it like
int lowerLimit = 1;
int upperLimit = 1000;
int res = lowerLimit.Solve(upperLimit, 3, 5);Any suggestions about the shown code are welcome.
Because math has closed its doors for me after finishing school, I don't know if there is any math trick to do this any faster or easier.
Solution
This is not so much of a code answer as a mathematical answer.
We can calculate directly the number of multiples \$m\$ of a natural number \$n\$ that are below the limit \$x\$. It's simply \$\lceil x/n\rceil\$. The sum of those multiples is:
$$n\sum_{i=1}^{\lceil x/n\rceil}= n\left(\frac{1}{2}(\lceil x/n \rceil)(\lceil x/n\rceil+1)\right)$$
So for \$n=3\$ and \$x=999\$, we get $$3\left(\frac{1}{2}(333)(333+1)\right)= 166833$$
And for \$n=5\$ and \$x=999\$, we get $$5\left(\frac{1}{2}(200)(200+1)\right)=99500$$
So we could calculate the answer is $$166833 + 99500 = 266333$$ However the problem here (hat tip to @MartinR !) is that we have double-counted multiples of 15. To fix that, we need to subtract that count:
$$ 15\left(\frac{1}{2}(66)(66+1)\right) = 33165$$
So the correct final answer is $$266333 - 33165 = 233168$$
We can calculate directly the number of multiples \$m\$ of a natural number \$n\$ that are below the limit \$x\$. It's simply \$\lceil x/n\rceil\$. The sum of those multiples is:
$$n\sum_{i=1}^{\lceil x/n\rceil}= n\left(\frac{1}{2}(\lceil x/n \rceil)(\lceil x/n\rceil+1)\right)$$
So for \$n=3\$ and \$x=999\$, we get $$3\left(\frac{1}{2}(333)(333+1)\right)= 166833$$
And for \$n=5\$ and \$x=999\$, we get $$5\left(\frac{1}{2}(200)(200+1)\right)=99500$$
So we could calculate the answer is $$166833 + 99500 = 266333$$ However the problem here (hat tip to @MartinR !) is that we have double-counted multiples of 15. To fix that, we need to subtract that count:
$$ 15\left(\frac{1}{2}(66)(66+1)\right) = 33165$$
So the correct final answer is $$266333 - 33165 = 233168$$
Context
StackExchange Code Review Q#115572, answer score: 10
Revisions (0)
No revisions yet.