CODEWITHSUNDEEP
java
Tloz
Tloz

Reputation: 349

find the sum of the multiples of 3 and 5 below 1000

Ok guys, so I'm doing the Project Euler challenges and I can't believe I'm stuck on the first challenge. I really can't see why I'm getting the wrong answer despite my code looking functional:

import java.util.ArrayList;


public class Multithree {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        ArrayList<Integer> x = new ArrayList<Integer>();
        ArrayList<Integer> y = new ArrayList<Integer>();
        int totalforthree = 0;
        int totalforfive = 0;

        int total =0;

        for(int temp =0; temp < 1000 ; temp++){
            if(temp % 3 == 0){
                x.add(temp);
                totalforthree += temp;
            }
        }

        for(int temp =0; temp < 1000 ; temp++){
            if(temp % 5 == 0){
                y.add(temp);
                totalforfive += temp;
            }
        }

        total = totalforfive + totalforthree;



        System.out.println("The multiples of 3 or 5 up to 1000 are: " +total);

    }

}

I'm getting the answer as 266333 and it says it's wrong...

Upvotes: 6

Views: 46288

Answers (14)

Samhita Argula
Samhita Argula

Reputation: 35

Just simply

public class Main
{
    public static void main(String[] args) {
        int sum=0;
        for(int i=1;i<1000;i++){
            if(i%3==0 || i%5==0){
                sum+=i;
            }
        }
        System.out.println(sum);
    }
}

Upvotes: 0

dreamcrash
dreamcrash

Reputation: 51463

Others have already pointed out the mistakes in your code, however I want to add that the modulus operator solution is not the most efficient.

A faster implementation would be something like this:

int multiply3_5(int max)
{
  int i, x3 = 0, x5 = 0, x15 = 0;
    
  for(i = 3; i < max; i+=3)    x3 += i;    // Store all multiples of 3
  for(i = 5; i < max; i+=5)    x5 += i;    //  Store all multiples of 5
  for(i = 15; i < max; i+=15)  x15 += i;   //   Store all multiples 15; 
 
  return x3+x5-x15;
}

In this solution I had to take out multiples of 15 because, 3 and 5 have 15 as multiple so on the second loop it will add multiples of 15 that already been added in the first loop;

Solution with a time complexity of O(1)

Another even better solution (with a time complexity of O(1)) is if you take a mathematical approach.

You are trying to sum all numbers like this 3 + 6 + 9 ... 1000 and 5 + 10 + 15 +20 + ... 1000 this is the same of having 3 * (1 + 2 + 3 + 4 + … + 333) and 5 * ( 1 + 2 + 3 + 4 + ... + 200), the sum of 'n' natural number is (n * (n + 1)) (source) so you can calculate in a constant time, as it follows:

int multiply3_5(int max)
{
   int x3 =   (max - 1) / 3; 
   int x5 =   (max - 1) / 5;
   int x15 =  (max - 1) / 15;                  
   int sn3 =  (x3 * (x3 + 1)) / 2; 
   int sn5 =  (x5 * (x5 + 1)) / 2; 
   int sn15 = (x15 * (x15 + 1)) / 2;
   return (3*sn3) + (5 *sn5) - (15*sn15);
}

Running Example:

public class SumMultiples2And5 {

    public static int multiply3_5_complexityN(int max){
        int i, x3 = 0, x5 = 0, x15 = 0;

        for(i = 3; i < max; i+=3)    x3 += i;    // Store all multiples of 3
        for(i = 5; i < max; i+=5)    x5 += i;    //  Store all multiples of 5
        for(i = 15; i < max; i+=15)  x15 += i;   //   Store all multiples 15;

        return x3 + x5 - x15;
    }

    public static int multiply3_5_constant(int max){
        int x3 =   (max - 1) / 3;
        int x5 =   (max - 1) / 5;
        int x15 =  (max - 1) / 15;
        int sn3 =  (x3 * (x3 + 1)) / 2;
        int sn5 =  (x5 * (x5 + 1)) / 2;
        int sn15 = (x15 * (x15 + 1)) / 2;
        return (3*sn3) + (5 *sn5) - (15*sn15);
    }

    public static void main(String[] args) {
        System.out.println(multiply3_5_complexityN(1000));
        System.out.println(multiply3_5_constant(1000));
    }
}

Output:

233168
233168

Upvotes: 1

Sunil Vishwakarma
Sunil Vishwakarma

Reputation: 21

    int count = 0;
for (int i = 1; i <= 1000 / 3; i++)
{
count = count + (i * 3);
if (i < 1000 / 5 && !(i % 3 == 0))
{
count = count + (i * 5);
}
}

Upvotes: 0

Parag Satav
Parag Satav

Reputation: 17

If number is 10 then multiple of 3 is 3,6,9 and multiple of 5 is 5,10 total sum is 33 and program gives same answer:

package com.parag;

/*
 * @author Parag Satav
 */
public class MultipleAddition {

    /**
     * @param args
     */
    public static void main( final String[] args ) {
    // TODO Auto-generated method stub

    ArrayList<Integer> x = new ArrayList<Integer>();
    ArrayList<Integer> y = new ArrayList<Integer>();
    int totalforthree = 0;
    int totalforfive = 0;
    int number = 8;

    int total = 0;

    for ( int temp = 1; temp <= number; temp++ ) {
        if ( temp % 3 == 0 ) {
            x.add( temp );
            totalforthree += temp;
        }

        else if ( temp % 5 == 0 ) {
            y.add( temp );
            totalforfive += temp;
        }
    }

    total = totalforfive + totalforthree;
    System.out.println( "multiples of 3 : " + x );
    System.out.println( "multiples of 5 : " + y );
    System.out.println( "The multiples of 3 or 5 up to " + number + " are: " + total );

}

}

Upvotes: -1

Widuranga
Widuranga

Reputation: 336

In a mathematical perspective,
You did not consider about common factors between 3 and 5.
Because there is double counting.


ex; number 15 , 30 , 45 , 60 , 75 , 90 , 105 , 120 , 135 , 150 , 165 , 180 , 195 , 210 , 225 , 240 , 255 , 270 , 285 , 300 , 315 , 330 , 345 , 360 , 375 , 390 , 405 , 420 , 435 , 450 , 465 , 480 , 495 , 510 , 525 , 540 , 555 , 570 , 585 , 600 , 615 , 630 , 645 , 660 , 675 , 690 , 705 , 720 , 735 , 750 , 765 , 780 , 795 , 810 , 825 , 840 , 855 , 870 , 885 , 900 , 915 , 930 , 945 , 960 , 975 , 990 , are common factors.

total of common factors = 33165.
Your answer is 266333
Correct answer is 233168.
Your Answer - Total of common factors
266333-33165=233168.

(this is a code for getting common factors and Total of common factors )

public static void main(String[] args) {

System.out.println("The sum of the Common Factors : " + getCommonFactorSum());

}

private static int getCommonFactorSum() {
int sum = 0;
for (int i = 1; i < 1000; i++) {
    if (i % 3 == 0 && i % 5 == 0) {
        sum += i;
        System.out.println(i);
    }
}

Upvotes: 2

Aniket Sahrawat
Aniket Sahrawat

Reputation: 12937

If you are using Java 8 you can do it in the following way:

Integer sum = IntStream.range(1, 1000) // create range
                  .filter(i -> i % 3 == 0 || i % 5 == 0) // filter out
                  .sum(); // output: 233168

To count the numbers which are divisible by both 3 and 5 twice you can either write the above line twice or .map() the 2 * i values:

Integer sum = IntStream.range(1, 1000)
                  .filter(i -> i % 3 == 0 || i % 5 == 0)
                  .map(i -> i % 3 == 0 && i % 5 == 0 ? 2 * i : i)
                  .sum(); // output: 266333

Upvotes: 1

Perry Thomson
Perry Thomson

Reputation: 9

I did this several ways and several times. The fastest, cleanest and simplest way to complete the required code for Java is this:

public class MultiplesOf3And5 {

public static void main(String[] args){

System.out.println("The sum of the multiples of 3 and 5 is: " + getSum());

}

private static int getSum() {
int sum = 0;
for (int i = 1; i < 1000; i++) {
    if (i % 3 == 0 || i % 5 == 0) {
        sum += i;
    }
}
return sum;
}

If anyone has a suggestion to get it down to fewer lines of code, please let me know your solution. I'm new to programming.

Upvotes: 0

Ritesh
Ritesh

Reputation: 21

How I solved this is that I took an integer value (initialized to zero) and kept on adding the incremented value of i, if its modulo with 3 or 5 gives me zero.

private static int getSum() {
int sum = 0;
for (int i = 1; i < 1000; i++) {
    if (i % 3 == 0 || i % 5 == 0) {
        sum += i;
    }
}
return sum;
}

Upvotes: 0

Surya Singh
Surya Singh

Reputation: 189

public class Solution {
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t>0){
            int sum = 0;
            int count =0;
            int n = sc.nextInt();
            n--; 
            System.out.println((n/3*(6+(n/3-1)*3))/2 + (n/5*(10+(n/5-1)*5))/2 - (n/15*(30+(n/15-1)*15))/2);
            t--;
    }
}
}

Upvotes: -1

Pankaj Prakash
Pankaj Prakash

Reputation: 2428

Don't you all think instead of using loops to compute the sum of multiples, we can easily compute sum of n terms using a simple formula of Arithmetic Progression to compute sum of n terms.

I evaluated results on both using loop and formula. Loops works simply valuable to short data ranges. But when the data ranges grows more than 1010 program takes more than hours to process the result with loops. But the same evaluates the result in milliseconds when using a simple formula of Arithmetic Progression.

What we really need to do is:
Algorithm :

  1. Compute the sum of multiples of 3 and add to sum.
  2. Compute the sum of multiples of 5 and add to sum.
  3. Compute the sum of multiples of 3*5 = 15 and subtract from sum.

Here is code snippet in java from my blog post CodeForWin - Project Euler 1: Multiples of 3 and 5

n--; //Since we need to compute the sum less than n.
//Check if n is more than or equal to 3 then compute sum of all divisible by
//3 and add to sum.  
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);

Upvotes: 1

Ojonugwa Jude Ochalifu
Ojonugwa Jude Ochalifu

Reputation: 27257

Okay, so this isn't the best looking code, but it get's the job done. 

public class Multiples {

public static void main(String[]args) {
    int firstNumber = 3;
    int secondNumber = 5;
    ArrayList<Integer> numberToCheck = new ArrayList<Integer>();
    ArrayList<Integer> multiples = new ArrayList<Integer>();
    int sumOfMultiples = 0;
    for (int i = 0; i < 1000; i++) {
       numberToCheck.add(i);

       if (numberToCheck.get(i) % firstNumber == 0 || numberToCheck.get(i) % secondNumber == 0) {
           multiples.add(numberToCheck.get(i));
       }

    }

    for (int i=0; i<multiples.size(); i++) {

     sumOfMultiples += multiples.get(i);

    }
    System.out.println(multiples);
    System.out.println("Sum Of Multiples: " + sumOfMultiples);

}

}

Upvotes: -1

Sunil MG
Sunil MG

Reputation: 1

Logics given above are showing wrong answer, because multiples of 3 & 5 are taken for calculation. There is something being missed in above logic, i.e., 15, 30, 45, 60... are the multiple of 3 and also multiple of 5. then we need to ignore such while adding.

    public static void main(String[] args) {
    int Sum=0, i=0, j=0;
    for(i=0;i<=1000;i++)
        if (i%3==0 && i<=999)
            Sum=Sum+i;
    for(j=0;j<=1000;j++)
        if (j%5==0 && j<1000 && j*5%3!=0)
            Sum=Sum+j;
    System.out.println("The Sum is "+Sum);
}

Upvotes: -1

Arash Saidi
Arash Saidi

Reputation: 2238

You are counting some numbers twice. What you have to do is add inside one for loop, and use an if-else statement where if you find multiples of 3, you do not count them in 5 as well. 

 if(temp % 3 == 0){
     x.add(temp);
     totalforthree += temp;
 } else if(temp % 5 == 0){
     y.add(temp);
     totalforfive += temp;
 }

Upvotes: -1

Todoy
Todoy

Reputation: 1266

you should use the same for loop for both to aviod double counting numbers that are multiple of both. such as 15,30...

   for(int temp =0; temp < 1000 ; temp++){
        if(temp % 3 == 0){
            x.add(temp);
            totalforthree += temp;
        }else if(temp % 5 == 0){
            y.add(temp);
            totalforfive += temp;
        }
    }

Upvotes: 13

Related Questions