HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpModerate

Solving Project Euler Problem 1 using extension methods

Submitted by: @import:stackexchange-codereview··
0
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 lowerLimit and an upperLimit returning an IEnumerable

public 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$$

Context

StackExchange Code Review Q#115572, answer score: 10

Revisions (0)

No revisions yet.