11
\$\begingroup\$

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<int>

public static IEnumerable<int> 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 < 0 || lowerLimit < 0) { throw new ArgumentOutOfRangeException("lowerLimit and upperLimit needs to be greater than or equal to 0"); }
        if (multiples == null || multiples.Length == 0) { return 0; }

        return lowerLimit.GetSequence(upperLimit)
            .Where(i => i.IsMultipleOf(multiples))
            .Sum();
    }

    private static bool IsMultipleOf(this int value, IEnumerable<int> 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.

\$\endgroup\$
10
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

Naming GetSequence

Some examples from for inspiration:

scala> 1.to(3)
res0: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)

scala> 1.until(3)
res1: scala.collection.immutable.Range = Range(1, 2)

Building on these examples, I suggest renaming GetSequence to Until.

Use The Math, @Heslacher ...

... well ok, in the case of one or two arguments, there's a simple math solution. Instead of iterating over the numbers in the range and performing modulo, you could:

  • Calculate the count of multiples in the range: int count = (target - 1) / multiple
  • Realize that the multiples form a sequence that can be simplified, for example:
    • 3, 6, 9, 12, ...
    • = 3 * (1, 2, 3, ...)
    • In that 1, 2, 3, ... sequence, we know that there are count terms. The formula to calculate the sum of such sequence is n * (n + 1) / 2

With a helper function:

private int SumOfMultiples(int target, int multiple) {
    int count = (target - 1) / multiple;
    return multiple * count * (count + 1) / 2;
}

This gives a straight \$O(1)\$ solution for one multiple. For two multiples a and b, you cannot simply sum them as that would include the multiples of their multiples twice. So after summing, you would have to subtract the multiples of a * b:

return SumOfMultiples(target, a)
    + SumOfMultiples(target, b)
    - SumOfMultiples(target, a * b);

Thanks for @MartinR for the hint, and @BorisTheSpider to point out the problem with my original answer that didn't subtract.

It's easy to handle two parameters like 3 and 5 in this example. But handling arbitrary number of parameters, the math gets a lot trickier.

In conclusion, when multiples.Length <= 2, a fairly simple math solution exists. When multiples.Length > 2 the implementation needs more work, and more math.

Your solution with iteration may be a bit inefficient, but it's simple and it works.

Input validation

In this code:

public static int Solve(this int lowerLimit, int upperLimit, params int[] multiples)
{
    if (upperLimit < 0 || lowerLimit < 0) { throw new ArgumentOutOfRangeException("lowerLimit and upperLimit needs to be greater than or equal to 0"); }
    if (multiples == null || multiples.Length == 0) { return 0; }

It seems to me the lowerLimit is given by the problem scope as 0, so no need to validate that. Instead of delegating the validation to GetSequence, it would be better to do that earlier, here in Solve, and GetSequence can safely assume to receive valid values. You can add an assert statement (if exists in C#, I don't know) to document your assumption, in case you might want to copy-paste the method to a utility library later.

I don't have a C# compiler with me now, but I venture a guess that multiples will only be null if a programmer explicitly passes a null. Which would be a programming error, much like passing in a negative upperLimit, so I suggest to throw an exception in this case.

\$\endgroup\$
  • \$\begingroup\$ Unless I am overlooking something, your "math using code" does not produce the correct answer to PE #1 :) \$\endgroup\$ – Martin R Jan 1 '16 at 15:36
  • \$\begingroup\$ @Janos - correct me if I'm wrong, but doesn't this double-count, for example, 15. Wouldn't you have to subtract the sequence of multiples of both 3 and 5 from the result? \$\endgroup\$ – Boris the Spider Jan 1 '16 at 18:55
  • \$\begingroup\$ Hey @BoristheSpider, for 3, you have count = 14 / 3 = 4, so adding 3 * 4 * 5 / 2 = 30, and for 5, you have count = 14 / 5 = 2, so adding 5 * 2 * 3 / 2 = 15, so total 45, which is equal to the target: 3 + 6 + 9 + 12 + 5 + 10, so that looks good to me \$\endgroup\$ – janos Jan 1 '16 at 19:05
  • \$\begingroup\$ @janos see the other answer - it describes the double counting issue in more detail. I think you need to have a target > the lower common multiple (i.e. > 15 in this case) for the problem to become apparent. \$\endgroup\$ – Boris the Spider Jan 1 '16 at 19:09
  • \$\begingroup\$ @BoristheSpider oh I see, from target = 16 starts the fun... You're right, the double-counting is a problem, makings things a lot more complicated with many more multiples than just the numbers 3 and 5. Thanks for pointing it out. \$\endgroup\$ – janos Jan 1 '16 at 19:28
5
\$\begingroup\$

You can simplify your IsMultipleOf method using Any from the System.Linq namespace:

private static bool IsMultipleOf(this int value, IEnumerable<int> multiples)
{
    return multiples.Any(multiple => value % multiple == 0);
}
\$\endgroup\$
4
\$\begingroup\$

That extension method GetSequence() kind of already exists in the Linq namespace as an extension method named Range() which takes a start and a count parameter. This only needs to be called using 1 as start and 999 as count because count is inclusive whereas we need to have the items 1..999 to check the natural numbers below 1000.

This Range() method can be integrated like so

public static IEnumerable<int> GetSequence(this int lowerLimit, int upperLimit)
{
    var upperLimitExclusive = upperLimit - 1;
    if (upperLimitExclusive < 0) { throw new ArgumentOutOfRangeException("upperLimit needs to be greater than 0"); }
    if (lowerLimit + upperLimitExclusive == int.MaxValue) { throw new ArgumentOutOfRangeException("lowerLimit + upperLimit -2 should not exceed int.MaxValue"); }

    return Enumerable.Range(lowerLimit, upperLimitExclusive);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Your second guard for > int.MaxValue can never be hit because an int can never be greater than max value. It will loop around to a negative value in unchecked operations (the default) or throw an error in a checked operation. \$\endgroup\$ – RobH Jan 1 '16 at 14:23
  • \$\begingroup\$ @RobH I thought because in the documentation it states "start + count -1 is larger than MaxValue." will have an `ArgumentOutOfRangeException" thrown. \$\endgroup\$ – Heslacher Jan 1 '16 at 14:26
  • \$\begingroup\$ You'll have to rearrange the condition so that you're not comparing to greater than max value or force the left hand side to be int64. Otherwise, the sum on the left will overflow to a negative and pass the check there and error in Enumerable.Range \$\endgroup\$ – RobH Jan 1 '16 at 14:28
  • 1
    \$\begingroup\$ I have changed it now to lowerLimit + upperLimitExclusive == int.MaxValue \$\endgroup\$ – Heslacher Jan 1 '16 at 14:29
1
\$\begingroup\$

This code:

public static IEnumerable<int> 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;
    }
}

Can be accomplished with:

var range = Enumerable.Range(lowerLimit, upperLimit);

It even throws an out of range exception so you can completely remove your If statement checking that in the Solve() method.

Now that you have an IEnumerable you can use LINQ:

return range.Where(i => i.IsMultipleOf(multiples)).Sum();

Heck you could go crazy and do a one-liner:

return Enumerable.Range(lowerLimit, upperLimit).Where(i => i.IsMultipleOf(multiples)).Sum();

I'd suggest using RobH's answer to simply your IsMultipleOf() method. I would also move your null check for multiples into the IsMultipleOf() method and if's null simply return false.

With all of this we'd be left with:

public static class SolverOfProblemOne
{
    public static int Solve (this int lowerLimit, int upperLimit, params int[] multiples)
    {
        return Enumerable.Range(lowerLimit, upperLimit).Where(i => i.IsMultipleOf(multiples)).Sum();
    }

    private static bool IsMultipleOf (this int value, IEnumerable<int> multiples)
    {
        return multiples != null && multiples.Any(multiple => value % multiple == 0);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.