Solving Project Euler Problem 1 using extension methods

Question

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.

Answer 1

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

Answer 2

Naming GetSequence

Some examples from scala 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.

Answer 3

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); } 

Answer 4

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); } 

Answer 5

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); } }