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);
    }
}
5
  • 1
    Related: stackoverflow.com/questions/3374622/…
    – jball
    Nov 9, 2010 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 9, 2010 at 19:00
  • 1
    The best solution in what regard? Speed, size, comprehensibility...? Nov 9, 2010 at 19:01
  • @sepp2k, Code review and alternative way. Like Matthew suggested one.
    – t0mcat
    Nov 9, 2010 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 9, 2010 at 19:07

13 Answers 13

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.

12
  • I think you're a little off. I got 334 * 999/2 + 200 * 995 / 2 - 67 * 990 / 2. Nov 9, 2010 at 19:42
  • 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 9, 2010 at 19:55
  • 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, 2010 at 12:35
  • 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, 2010 at 14:34
  • 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, 2010 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.

1
  • 1
    Thanks Matthew. I am looking for suggestion like yours.
    – t0mcat
    Nov 9, 2010 at 19:03
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

1
  • 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, 2011 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.

6
  • @Ishtar: Oops, typo. Fixed. Thanks.
    – Jay
    Nov 10, 2010 at 14:26
  • what are your thoughts on using a hashset to avoid checking for the modulus duplicate case?
    – David T.
    May 5, 2014 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 5, 2014 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, 2014 at 4: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, 2014 at 13:29
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
}
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)
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);
    }
}
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()
0
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.

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

-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);
    }
1
  • 1
    This is (almost) the same as the program in the question. What do you want to say?
    – Glorfindel
    Aug 3, 2015 at 19:08

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