7

I just started with solving Project Eulers problems. Even though this one is very simple. I want to take your opinion on the best solution.

The problem:

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.

This is how I coded it:

package com.problem.one.ten;
public class NaturalNumber {

    public static void main(String args[])  {
        int sum=0;
        for(int i=0; i<1000; i++) {
            if((i%3 == 0) || (i%5 == 0)){
                sum += i;
            }
        }
        System.out.println(sum);
    }
}
t0mcat
  • 5,511
  • 19
  • 45
  • 58
  • 1
    Related: http://stackoverflow.com/questions/3374622/project-euler-problem-1-possible-refactorings-and-run-time-optimizations – jball Nov 09 '10 at 19:00
  • 5
    Are you asking for a code review or a list of alternative ways to solve the problem? In the latter case you should just look at the forum-discussion attached to the problem, which includes plenty of alternative solutions. – sepp2k Nov 09 '10 at 19:00
  • 1
    The best solution in what regard? Speed, size, comprehensibility...? – Anonymous Coward Nov 09 '10 at 19:01
  • @sepp2k, Code review and alternative way. Like Matthew suggested one. – t0mcat Nov 09 '10 at 19:03
  • I went ahead and added the question text as well. No point in people linking through to another site for 180 bytes of info. – jball Nov 09 '10 at 19:07

13 Answers13

28

A better solution is a simple application of inclusion-exclusion principle. The sum of all numbers we are interested in is (1) the sum of all numbers divisible by 3, plus (2) the sum of all numbers divisible by 5, minus (3) the sum of all numbers divisible by 15. Each of the 3 sums is a sum of an arithmetic progression, which is relatively easy to find. Basically, you don't need a loop.

The number of non-negative integers divisible by n below N is exactly [(N - 1) / n] + 1. The maximal such number is n * ([(N - 1) / n], therefore by the arithmetic progression sum formula, their sum is [(N - 1) / n] * ([(N - 1) / n] + 1) * n / 2.

For our case, we have got:

  1. N = 1000, n = 3, [(N - 1) / n] = 333, sum = 333*334*3/2.
  2. N = 1000, n = 5, [(N - 1) / n] = 199, sum = 199*200*5/2.
  3. N = 1000, n = 15, [(N - 1) / n] = 66, sum = 66*67*15/2.

The final result is 233168.

Perhaps an even better solution exists.

Vlad
  • 35,022
  • 6
  • 77
  • 199
  • I think you're a little off. I got `334 * 999/2 + 200 * 995 / 2 - 67 * 990 / 2`. – Matthew Flaschen Nov 09 '10 at 19:42
  • There's an error in your calculations; it's 333*334*3/2, not 333*332*3/2 (and analogous for 5 and 15) – Luke Hutteman Nov 09 '10 at 19:43
  • Just to nitpick, the problem says "below 1000", not "below or equal to 1000", so there are only 199 multiples of 5, not 200. – Jay Nov 09 '10 at 19:54
  • 1
    @Jay: I'm including 0 as well, for simplicity. It doesn't actually change the sum. That's why I write "non-negative numbers" and not just "positive" – Vlad Nov 09 '10 at 19:55
  • This is only better if N is much bigger than 1000, because it is more complex. – starblue Nov 10 '10 at 08:38
  • 1
    @starblue: there is no "better" or "worse". Pragmatically speaking, any solutions which produces correct result in finite time is acceptable. There is an aesthetic value in the designing not a more efficient and sophisticated solution. There is a pure aesthetic value in designing the fastest possible algorithm. The following code: `if (1 % 3 == 0) || 1 % 5 == 0) count++; if (2 % 3 == 0) || 2 % 5 == 0) count++; ... if (999 % 3 == 0) || 999 % 5 == 0) count++;` is correct, too, and is even simpler. :-P – Vlad Nov 10 '10 at 12:35
  • @Vlad: But I see that despite saying your original formula was correct, you updated it. :-) – Jay Nov 10 '10 at 14:30
  • 3
    @Vlad: "any solutions which produces correct result in finite time is acceptable". I have to disagree. A program that requires 1,000 years to run is surely inferior to one that runs in 1 second, especially if I want to use the results in my lifetime. A program to determine the proper trajectory of an anti-missile defense is useless if it does not come up with an answer before the incoming missile hits. – Jay Nov 10 '10 at 14:34
  • @Jay: yes, I was wrong at the beginning. But I started updating the answer before the commentors found it :-) – Vlad Nov 10 '10 at 17:09
  • @Jay: From my personal point of view, an efficient program is better than an inefficient one. As you see, I tried to make the solution as efficient as possible. (Perhaps the more efficient though still correct solution would be just `cout << "233168" << endl`) But as long as the efficiency (speed, memory etc.) is not one of the acceptance criteria, this is just my personal opinion. For anti-missile program the speed is clearly an important criterion, so a fast program is a good one! – Vlad Nov 10 '10 at 17:13
  • Efficiency is just one quality criterion among many. It is better to choose a simpler solution if it is fast enough for the purpose, because it is more likely to be correct, easier to understand and maintain. On a modern desktop a loop up to 1000 runs in under a millisecond, so there's no point in optimizing that. For a loop up to say 10^12 this would be a completely different story. – starblue Nov 10 '10 at 21:20
  • 1
    @starblue: ease of understanding depends a lot of the reader's algorithmical and mathematical etc. background. In any case, the quality criteria should be defined in advance, and they can be different depending on the practical application. For particularly our case, I personally would see 1000 as just an arbitrary number, therefore I tried to make a solution which would work efficiently for a broader range of input numbers. Other people's understanding of what is actually needed may of course be different. – Vlad Nov 10 '10 at 21:39
11

It looks fine, though I would put sum in main. It's not a big deal on such a simple program. But in general, you should declare variables in the narrowest possible scope.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
6

While I'm sure there is an O(1) solution to this problem, figuring it out would not be worth the effort considering you're only asked to provide the answer for 1000.

I agree with Matthew that sum should be a local variable, but otherwise, your code looks fine to me as well.

solution without code (just for fun):

Using the fact that sum(1+2+3+...+n) = n(n+1)/2, we can derive that the sum of multiples of x below 1000 is floor(1000/x)*(floor(1000/x)+1)/2*x.

The answer we need is the sum of multiples of 3 below 1000, plus the sum of multiples of 5, minus the sum of multiples of 15 (which would otherwise be doublecounted).

There are 999/3 = 333 multiples of 3 below 1000, 999/5 = 199 multiples of 5 below 1000, and 999/15 = 66 multiples of 15 below 1000

So the sum of all multiples of 3 below 1000 = 333*334/2*3 = 166833, the sum of multiples of 5 below 1000 = 199*200/2*5 = 99500, and the sum of multiples of 15 below 1000 = 66*67/2*15 = 33165

Making the answer 166833 + 99500 - 33165 = 233168

Luke Hutteman
  • 1,921
  • 13
  • 11
  • Loop versus no-loop solutions raise an interesting point: The no-loop solutions are faster, but harder to verify. In general I'd take the time to test and verify, but the slower, "more obvious" solution would be preferable if you only need to run the program once and the run-time would be less than the time it would take to verify the more complex program. Debatable in cases where accuracy is vital and verification is difficult. – Jay Oct 31 '11 at 16:48
6

Your solution is the logically simplest and thus easiest to verify. Analytical solutions like Vlad's and Luke's are most efficient.

But for what it's worth, my first thought when I saw the problem was:

public int doit()
{
  int sum=0;
  for (int n=0;n<1000;n+=3)
  {
    sum+=n;
  }
  for (int n=0;n<1000;n+=5)
  {
    if (n%3!=0) // Don't pick up the 3's twice
      sum+=n;
  }
  return sum;
}

This would be more efficient than your solution as it would skip over numbers we know we're not interested in. And it's still intuitively pretty obvious how it works.

A no-loop solution is better, but I post this just because I have a meeting in 5 minutes and I was already here.

Jay
  • 26,876
  • 10
  • 61
  • 112
  • @Ishtar: Oops, typo. Fixed. Thanks. – Jay Nov 10 '10 at 14:26
  • what are your thoughts on using a hashset to avoid checking for the modulus duplicate case? – David T. May 05 '14 at 11:13
  • 1
    @davidt That would surely be less efficient. To retrieve a value from a hashset, Java gets the hash key of the value, takes that number modulo the number of entries in the hashset, and retrieves the entry at that location in an array. The entry is a linked list, which it then chases to see if the original value it is looking for is present. Note that one step in the process is calculating a modulo, and in addition to that there are a bunch of other steps. So it would have to take longer than just doing one modulo. – Jay May 05 '14 at 13:34
  • @Jay totally right. i didn't really think enough about what was happening underneath the covers (the code just looked cleaner). but actually now thinking about your solution in terms of your efficiency, i thought of one further optimization -> you could just subtract multiples of 15 instead of checking for `n%3`. when you check for the modulous, you have to do that on each iteration of incrementing by 5. but you could save 66% calculations if you just only subtracted the summed multiples of 15. i believe division/modulo is slightly more costly down at the digital circuit level as well – David T. May 20 '14 at 04:13
  • @DavidT. You mean instead of checking for n%3!=0 in the second loop, have a third loop of n=0;n<1000;n+=15 ... sum-=n ? Interesting idea. That would mean having the overhead of an extra loop, but it would eliminate the modulo. I'd guess that you're right, that it would be faster. 'Have to study the generated code or do an experiment to be sure. – Jay May 20 '14 at 13:29
  • @Jay yes exactly - i'm actually not very familiar with how much overhead the extra loop creation overhead is, but i'd imagine it shouldn't be more costly than iterating 200 times checking for `n%3!=0`. but either way, i think your solution is efficient enough already, esp for 5 min of effort. thnx for the discussion! :) – David T. May 20 '14 at 18:11
3

I did that using the arithmetic progression with O(1). Here's my solution and it worked for values more that 1000 too till 10^9 like

long sum1=0,sum2=0,sum3=0,sum=0;
            long no3=0,no5=0,no15=0;

            //find the no of terms 
            no3=(array[i]-1)/3;
            no5=(array[i]-1)/5;
            no15=(array[i]-1)/15;

            //find the sum of the terms 

            sum1=no3*(6+(no3-1)*3)/2 ;
            sum2=no5*(10+(no5-1)*5)/2;
            sum3=no15*(30+(no15-1)*15)/2;
            sum=sum1+sum2-sum3;

            System.out.println(sum);
        }
2

For Project Euler I have this one advice: go functional.

I had previously solved about 100 problems in Java, but I had struggled with many along the road, and I had to write a lot of library code. I recently started solving them in Scala, starting from Problem 1 again, and it feels much more natural.

Besides the fact that you can solve the first few problems with just pen and paper, as pointed out on other answers, solving this one using a functional language is very simple and easy to come up with. This is my solution from problem 1:

object Problem001 {
    def main(args: Array[String]) = println(find(1000))

    def find(max:Int) =
        Stream.from(1) filter (n => n % 3 == 0 || n % 5 == 0) takeWhile (_ < max) sum
}
djjeck
  • 1,781
  • 17
  • 25
1

Vlad's solution rules.
But here' another along the lines of what Jay posted, but with 1 loop

def ProjectEuler1(upper_limit):
    num_3mult = (upper_limit-1)//3  # total multiples of 3, less than upper_limit
    num_5mult = (upper_limit-1)//5  # total multiples of 5, less than upper_limit
    sum_multiples = 0
    for i in range(1,num_3mult+1):
        sum_multiples += i*3
        if i <= num_5mult and i%3!=0: # only add the multiples of 5 which are not multiple of 3 (to avoid adding duplicates)
            sum_multiples += i*5
    print('Sum of all multiples of 3 and 5 below 1000 = ', sum_multiples, end='\n')

ProjectEuler1(1000)
yash
  • 187
  • 7
1

I was solving the problem and came up with the solution that @vlad has mentioned. Quite thrilled about it(never heard of the inclusion-exclusion principle). Here is my code:

public class Prob1 {
    public static int sumOfMultiples(int i, int j, int limit){
        int s = --limit / i, t = limit / j, u = limit / (i * j);
        return (i*(s*(s+1)/2)) + (j*(t*(t+1)/2)) - ((i*j)*(u*(u+1)/2));
    }
}

Test:

public class TestProb1 {

    @Test
    public void testSumOfMultiples(){
        int actual = Prob1.sumOfMultiples(3, 5, 10);
        assertEquals(23, actual);

        actual = Prob1.sumOfMultiples(3, 5, 30);
        assertEquals(195, actual);

        actual = Prob1.sumOfMultiples(3, 5, 1000);
        assertEquals(233168, actual);
    }
}
ChrisOdney
  • 6,066
  • 10
  • 38
  • 48
0

You can solve this in .NET with a single LINQ expression

Dim sum = (From num In Enumerable.Range(1, 999)
           Where num Mod 3 = 0 OrElse num Mod 5 = 0
           Select num).Sum()
Shawn
  • 970
  • 11
  • 9
0

well the obvious arithmetic series sumation is:

int s=0,n,N=1000;
n=(N-1)/ 3; s+= 3*n*(n+1);  
n=(N-1)/ 5; s+= 5*n*(n+1);
n=(N-1)/15; s-=15*n*(n+1); s>>=1;
// can further optimize by precomputing N-1, n+1 to some temp vars
// also multiplication can be shift added instead

I saw some suma fors here and why to heck are you people

  • use division for suma ???
  • use +1 increment for +3i and +5i multiplicants ???

try this instead:

int s=0,N=1000;
for (int i=0;i<N;i+=5) s+=i;
for (int i=0,j=0;i<N;i+=3,j++) if (j==5)  j=0; else s+=i;

I know is trivial but hopefully helps someone to realize how to write things better.

Spektre
  • 49,595
  • 11
  • 110
  • 380
0

Week 5 of my first JAVA course... this is how I would solve it ;) it's a real piece de triomphe

import java.util.Scanner;
 public class Counter {
 public static void main(String args[]) {

System.out.println("Enter an integer, and COUNTER will find the sum of all the multiples of THREE and FIVE:");
int entry;
Scanner input = new Scanner(System.in);
entry = input.nextInt();

int three = 0;
int threeOut = 0;
int threeOpTot = (entry / 3);
int threeOp = 0;

while( threeOp < threeOpTot) {
three = three + 3 ;
threeOut = three + threeOut ;
threeOp += 1;
System.out.println(threeOp + " times 3 is " + three + ". ");
System.out.println("     " + threeOut + ", is the total sum of " + threeOp + "/" +
 threeOpTot + " threes");
}

int five = 0;
int fiveOut = 0;
int fiveOpTot = (entry / 5);
int fiveOp = 1;

while( fiveOp < fiveOpTot) {
five = five + 5 ;
fiveOut = five + fiveOut ;
fiveOp += 1 ;
System.out.println(threeOp + " times 3 is " + three + ". ");
System.out.println("     " + threeOut + ", is the total sum of " + 
threeOp + "/" + threeOpTot + " threes");
}


int fifteen = 0;
int fifteenOut = 0;
int fifteenOpTot = (entry / 15);
int fifteenOp = 0;

while( fifteenOp < fifteenOpTot) {
fifteen = fifteen + 15 ;
fifteenOut = fifteen + fifteenOut ;
fifteenOp += 1 ;


System.out.println(fifteenOp + " times fifteen is " + fifteen + ".");
System.out.println("     " + fifteenOut + ", is the total sum of " + fifteenOp +
 "/" + fifteenOpTot + " fifteens");
}

System.out.println("The final values of threes' are " + (threeOut) );
System.out.println("The final values of five' are " + (fiveOut) );
System.out.println("The sum of the over-lapping 15 factors are " + (fifteenOut) );
System.out.println("Grand total: " + (fiveOut + threeOut - fifteenOut) );
}
}
Baddy
  • 1
  • 1
0

That algorithm would work fine but don't you think it's not an optimal algorithm.

Here a simple logic of finding sum of n elements would do the trick and this algorithm would work on huge data also.

Here is a code snippet from my program at my blog CodeForWin - Project Euler 1: Multiples of 3 and 5

n--; //Since we need to compute sum of multiples below n  

if(n>=3) {  
    totalElements = n/3;  
    sum += (totalElements * ( 3 + totalElements*3)) / 2;  
}  

//Check if n is more than or equal to 5 then compute sum of all elements   
//divisible by 5 and add to sum.  
if(n >= 5) {  
    totalElements = n/5;  
    sum += (totalElements * (5 + totalElements * 5)) / 2;  
}  

//Check if n is more than or equal to 15 then compute sum of all elements  
//divisible by 15 and subtract from sum.  
if(n >= 15) {  
    totalElements = n/15;  
    sum -= (totalElements * (15 + totalElements * 15)) / 2;  
}  

System.out.println(sum);    

This algorithms computes sum of n=1000000000000 in fraction of milliseconds.

Pankaj Prakash
  • 2,300
  • 30
  • 31
-1
public static void main(String[] args) {
        int sum = 0;
        int i = 0;
        while (i < 1000) {

            if (i % 3 == 0 || i % 5 == 0) {
                sum = sum + i;
            }
            i++;
        }
        System.out.println("Sum is " + sum);
    }