Project Euler Problem 1 Solution in C#
Christopher Tobin
February 07, 2020
On this page is the solution for Problem 1 of Project Euler. If you want just analysis about this problem, check it out here. Turn back now if you do not want the solution.
If you want a refresher about what is being asked:
Multiples of 3 and 5
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.
Test Driven Development
The minds behind Project Euler have been so thoughtful as to grace us with an example. This allows us to begin our journey by writing a unit test to account for the case described in the example. The test will pass 10 as the input parameter to some function and will expect a value of 23 to be returned.
[TestMethod]
public void Problem1_Example()
{
// Arrange
const int input = 10;
// Act
var result = Problem1.Solve(input);
// Assert
Assert.AreEqual(23, result);
}
Now that we have our test written for the example case, we’ll need to write some code to make the test pass. First we’ll need a class and a method. I’ll be making both the class and the method static because we won’t have a need to ever create an instance of this class.
public static class Program1
{
public static int Solve(int input)
{
// TODO: implementation here...
}
}
We could of course cheat and do something real cheesy. After all, the whole point of test driven development is to write the simplest solution to satisfy the test right?
public static int Solve(int input)
{
return 23;
}
When we run the test it passes! That’s good right? Of course not. This is complete crap. If we pass a value of 1000 into this method it will still return a value of 23, which is most definitely not correct. We can add an additional test to verify that when the method input is 1000, we don’t receive the value of 23 back.
[TestMethod]
public void Problem1_Answer()
{
// Arrange
const int input = 1000;
// Act
var result = Problem1.Solve(input);
// Assert
Assert.AreNotEqual(23, result);
}
This test fails like we expect it to. We don’t know the actual value to expect back yet so we can’t assert anything else at this point. These tests will provide a good foundation for moving forward with solving the problem.
Solving the Problem
A simple implementation for the solution to this problem is to use a loop to iterate over all of the numbers between 1 and whatever the value of the input variable is. The most common choices for loops are a for loop and a while loop. Either would work in this scenario but a for loop is the best choice here because there is a defined number of iterations. When we know that the loop will iterate for a defined amount of times, a for loop is the obvious choice. We’ll go through the loop up to the number specified in the input variable.
public static int Solve(int input)
{
for(var number = 1; number < input; number++)
{
// implementation...
}
}
Now that we have the loop, we need to fill it with stuff. We’ll first check if the number is divisible by 3. We’ll also need to keep track of all of the numbers that are divisible by either 3 or 5 so that we can add them up once we get to the end.
public static int Solve(int input)
{
var numbersDivisibleBy3or5 = new List<int>();
for (var number = 1; number < input; number++)
{
var isNumberDivisibleBy3or5 = false;
if (number % 3 == 0)
{
// This number is divisible by 3!
isNumberDivisibleBy3or5 = true;
}
else
{
// This number is not divisible by 3!
isNumberDivisibleBy3or5 = false;
}
if (isNumberDivisibleBy3or5)
{
numbersDivisibleBy3or5.Add(number);
}
}
}
There are a few things going on here:
- A list of
inthas been added so that we can keep track of the numbers divisible by either 3 or 5 - We execute an
ifstatement to check if the number is divisible by 3- We do this by using the
modoperator (%) - The
modoperator will output the remainder. When this expression outputs0, we know that the number is divisible by 3. - More info about this operator can be found on the Microsoft Documentation site.
- We do this by using the
- Whenever a number is divisible by 3, a local boolean variable
isNumberDivisibleBy3or5is set to true - When a number is not divisible by 3, we set
isNumberDivisibleBy3or5to false
That seems like a good start right? Now that we have all of the numbers that are divisible by 3, we can proceed to determining the numbers divisible by 5.
public static int Solve(int input)
{
var numbersDivisibleBy3or5 = new List<int>();
for (var number = 1; number < input; number++)
{
var isNumberDivisibleBy3or5 = false;
if (number % 3 == 0)
{
// This number is divisible by 3!
isNumberDivisibleBy3or5 = true;
}
else
{
// This number is not divisible by 3!
isNumberDivisibleBy3or5 = false;
}
if (number % 5 == 0)
{
// This number is divisible by 5!
isNumberDivisibleBy3or5 = true;
}
else
{
// This number is not divisible by 5!
isNumberDivisibleBy3or5 = false;
}
if (isNumberDivisibleBy3or5)
{
numbersDivisibleBy3or5.Add(number);
}
}
}
Easy peasy! We should now have all of the numbers divisible by either 3 or 5 in a list. All we need to do is add them all up and return the result. But how can we add all of the numbers in the list? One way would be to loop through this list and add each number to the previous one like so:
var total = 0;
foreach (var divisibleNumber in numbersDivisibleBy3or5)
{
total += divisibleNumber;
}
return total;
Bugs Everywhere
This should work right? If we run the test covering the example we actually see something unexpected - a failed test. Instead of the expected value of 23, we’re getting a value of 5. How on Earth is that happening??
There’s actually a bug in the code. Any time a number is not divisible by either 3 or 5, the isNumberDivisibleBy3or5 variable is being set to false. That’s correct behavior right? Well, not necessarily.
When a number is divisible by 3, isNumberDivisibleBy3or5 is set to true, which is what we expect. However, when we check if this same number is also divisible by 5, we are running into some problems when the number is not divisible by 5. Whenever a number is not divisible by 5, isNumberDivisibleBy3or5 is being set to false. Even if that number was already divisible by 3!
This is pretty simple to fix. All we need to do is remove the else condition when evaluating if a number is divisible by 3 or 5.
for (var number = 1; number < input; number++)
{
var isNumberDivisibleBy3or5 = false;
if (number % 3 == 0)
{
// This number is divisible by 3!
isNumberDivisibleBy3or5 = true;
}
if (number % 5 == 0)
{
// This number is divisible by 5!
isNumberDivisibleBy3or5 = true;
}
if (isNumberDivisibleBy3or5)
{
numbersDivisibleBy3or5.Add(number);
}
}
This fixes the bug and now the test for the example case passes!
Make it Better
Now that we’ve made a working solution, we can attempt to make it better. There are a few optimizations that can be made. The great thing about doing this is that we already have passing unit tests. After we make changes we can re-run the test to ensure we haven’t broken anything.
Unnecessary Looping
We’re currently doing some unnecessary looping at the end of the method to return the sum of all of the numbers divisible by 3 or 5. We can optimize this by keeping a running total of the sum of all numbers divisible by 3 or 5 as we go instead of storing them in a temporary list.
public static int Solve(int input)
{
var sum = 0;
for (var number = 1; number < input; number++)
{
if (number % 3 == 0)
{
// This number is divisible by 3!
sum += number;
}
if (number % 5 == 0)
{
// This number is divisible by 5!
sum += number;
}
}
return sum;
}
Multiple if Statements
We have 2 separate if statements at the moment: one to see if the number is divisible by 3 and a different one to see if the number is divisible by 5. We can combine these into one if statement with the OR (||) operator to make it a bit cleaner.
public static int Solve(int input)
{
var sum = 0;
for (var number = 1; number < input; number++)
{
if (number % 3 == 0 || number % 5 == 0)
{
// This number is divisible by 3 or by 5!
sum += number;
}
}
return sum;
}