Add multiples of 3 or 5 below 1000, Can this code be optimised. Project Euler #1

Question

I have seen some solution here for the same problem, this and this I have found better ways to solve this problem. I just want to know how good or bad my code and way of approaching this problem is.

using System;

public class Program
{
    public static void Main()
    {
        int sum = 0;
        for (int i = 0; 3 * i < 1000; i++)
        {
            sum += 3 * i;

            if (5 * i < 1000 && (5 * i) % 3 != 0)
            {
                sum += 5 * i;
            }
        }
        Console.WriteLine(sum );
    }

Answer 1

The main problem

The main issue here is that you define i in function of it being a "factor of 3", and then also try to use this number as a "factor of 5". This doesn't make any sense - as there is no inherent relationship between being a threefold and a fivefold number.

It would've made sense if you were doing it for 3 and 6, for example, because 3 and 6 are related:

//i*3 is obviously always a multiple of 3
sum += 3 * i;

if ((3*i) % 2 == 0)
{
    //Now we know that i*3 is also a multiple of 6
}

But that is not the case here.

---

The for loop's readability

I understand your idea, you wanted to only iterate over factors of three which keep the multiple under 1000. While I will suggest to change this approach (later in the answer), your approach could've been written in a much more readable manner:

for( int i = 0 ; i < 1000 ; i+=3 )

This will iterate over i values of 0,3,6,9,12,15,... and will skip all values inbetween.

The benefit here is that you don't need to work with i*3 all the time, you can just use i itself.

You will need to iterate over the multiple of 5 separately. However, should you keep using this approach, I would always suggest splitting these loops anyway.

---

The algorithm

Your approach works, but it's not the easiest approach. If I put your approach into words:

Add every multiple of 3 to the sum.

Also add the multiple of 5, but only if it's still below 1000, and it's not already divisble by 3.

The issue here is in how you handle the multiples of five. You're working with an i that is defined as the allowed values for threefolds. For any i > 200, you're effectively having to manually exclude this value. You're using a different approach for the 5 than you are using for the 3, even though the logic is exactly the same. That's not a reusable approach.

Secondly, there is a readability problem. Your code should be trivially readable, and I simply wasn't able to understand your intention. I had to google what the question was before I could understand what your code was trying to achieve.

So let me offer a better approach, first putting it into words:

• Check every number from 0 to 1000 (not including 1000)
• If it is divisible by 3 or it is divisible by 5, then add it to the sum.

This can be put into code, step by step:

// Check every number from 0 to 1000 (not including 1000)
for(int i = 0; i < 1000; i++)
{
    var isDivisibleBy3 = i % 3 == 0;
    var isDivisibleBy5 = i % 5 == 0;

    //If it is divisible by 3 or it is divisible by 5
    if(isDivisibleBy3 || isDivisibleBy5)
    {
        //then add it to the sum
        sum += i;
    }
}

Note how the code exactly mirrors my algorithm description.

You don't need to use the booleans. I simply added them to simplify the example. if(i % 3 == 0 || i % 5 == 0) would be equally okay to use because it's still reasonably readable.

If the calculations become more complex, I suggest always using the booleans so you neatly break your algorithm down to small and manageable steps. It will do wonders for your code readability, and it does not impact performance (the compiler will optimize this in a release build).

---

A LINQ variation

This can be further shortened using LINQ:

var sum = Enumerable.Range(0,1000)
              .Where(i => i % 3 == 0 || i % 5 == 0)
              .Sum();

LINQ is just a nicer syntaxt, but it uses a for/foreach iteration in the background, so I suspect it won't be much more performant than the previous example. But I do consider this highly readable.

---

Maximizing performance

The previous suggestion maximizes readability, but it does so at the cost of performance, as it now has to loop over 1000 values and evaluate them all. You already linked several other answer that clearly dive deeper into the code in order to maximize the performance, I hope you can see that this dramatically impacts the readability.

For example:

public void Solve(){
    result = SumDivisbleBy(3,999)+SumDivisbleBy(5,999)-SumDivisbleBy(15,999);
}

private int SumDivisbleBy(int n, int p){
    return n*(p/n)*((p/n)+1)/2;
}

By itself, I would have no idea what this code does. I can sort of understand the intention of Solve(), but it's not quite apparent how SumDivisbleBy() works.

SumDivisbleBy() has effectively become impossible to maintain. If you needed to introduce a change, you would effectively have to reverse engineer it before you can alter it. This means that starting from scratch is the better option, which is clearly not a good thing.

However, when performance is the main focus, this is acceptable. I would, however, strongly urge you to document the algorithm in comments specifically to help future readers in understanding how/why this works.

Note that AlanT's answer contains a more readable variant of the SumDivisbleBy() method, which already helps a lot with understanding the algorithm. The clear naming used clarifies what the algorithm does, which is the main goal of writing readable code (explaining why something works is only a secondary goal and not always required).

Answer 2

I'm afraid that the solution given is not better than the referenced C one (although the C solution could be generalized and made a bit easier to understand)

Why?

The code under review has a outer loop that is executed 333 times (with a multiplication in each condition check). We can remove the multiplication to do the job a bit more cheaply

for (int i = 1; i <= 333; i++)

But, even with the restructured loop we still do

this, sum += 3 * i;, 333 times and then
this, 5 * i < 1000 && (5 * i) % 3 != 0, 333 times

As opposed to

S1= a*(b+c)/2;, once
s2= k*(i+j)/2;, once
s3= n*(m+o)/2;, once
S= S1 + s2 - s3;, once

It is a bit of a cheat in the C solution that the various magic numbers are hardcoded; but even allowing for a function to calculate the values

var sum3 = SumDivisibleBy(999,3);
var sum5 = SumDivisibleBy(999,5);
var sum15 = SumDivisibleBy(999,15);
var sum35 = sum3 + sum5 - sum15;


private static int SumDivisibleBy(int range, int divisor)
{
    var top = range/divisor;
    var ret = divisor*top*(top+1)/2;
    return ret;
}

is a lot cheaper than brute-forcing the solution.

In the original solution, for numbers under 1000, we need to loop 333 times, for numbers under 10000, we need to loop 3333 times,... It doesn't scale well. For the other solution, there are the same number of operations each time.

Answer 3

Thanks @Henrik Hansen it helped. This is optimised code below according to the WIKI. But here is the tradeoff, this has to loop 1000 times. where above solution need to run at most 333 times.

 using System;

    public class Program
    {
        public static void Main()
        {
            int sum = 0;
            for (int i = 0; i < 1000; i++)
            {
                if ( i % 3 == 0 || i % 5 == 0)
                {
                    sum += i;
                }
            }
            Console.WriteLine(sum );
        }
    }

Answer 4

i=0
i++
if i%3 OR i%5 then sum+=i
else if i%15 then sum-=i

---

By the way this would be hardcoded. If you want reusable then wouldn't you:

i=0
i++
a = (user input)
b = (user input)
if i%a OR i%b then sum+=i
else if i%(a*b) then sum-=i

---

Or something similar to that. Or does this code already account for the duplicate sums. example you don't want to 15+15 because you only need one 15.