# Project Euler | Problem 1 | Multiples of 3 or 5

##
__Problem Description__ :

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.

Project Euler Problem 1 |

##
__Concept__ :

### X is multiple of Y if X%Y=0.

##
__Java Program__ :

##
__Output__ :

Output - Project Euler Problem 1 |

##
__References__ :

*Thank you friends, I hope you have clearly understood the solution of this problem. If you have any doubt, suggestion or query please feel free to comment below. You can also discuss this solution in our forum.***Tags : Project Euler Problem 1 Solution, Mathematics Problems, Solution in Java, for loop, if statement.**

Project Euler | Problem 1 | Multiples of 3 or 5
Reviewed by Rohit Agarwal
on
10/23/2016
Rating:

Hi Rohit,

ReplyDeleteI have something to say about the solution. No doubt solution is correct

but this solution will take lot of time if the number is greater(eg 1 billion)

It is good if optimized the code so that it can run efficiently for larger numbers also

lets first try to find out the pattern (i.e pattern of the required numbers)

(starting with 0)

3,5,6 9,10,12,15

18,20,21, 24,25,27,30

now lets say divide these numbers into two columns

col1 col2

3,5,6 9,10,12,15

18,20,21, 24,25,27,30

pattern in col1(starting n=0)

row1

n+3=3

n+5=5

n+6=6

row 2(n=15)

n+3=18

n+5=20

n+6=21

pattern in col2(starting n=6)

row1

n+3=9

n+4=10

n+6=12

n+9=15

row 2(n=21)

n+3=24

n+4=25

n+6=27

n+9=30

Now code it:

public class Program1{

public static void main(String[] args) {

int sum=0;

int num =0,i=1;

while(num<1000){

if(num+3<1000)

sum=sum+num+3;

if(i==1)

{

if(num+5<1000)

sum=sum+num+5;

}

else if(num+4 <1000)

sum=sum+num+4;

if(num+6<=1000)

sum=sum+num+6;

if(i==0){

if(num+9<1000)

sum=sum+num+9;

i=1;

num+=9;

}

else{

i=0;

num+=6;

}

}

System.out.println("\nThe sum of all multiples of 3 or 5 below 1000 is : "+sum);

}

}

For any doubts and update pls comment...

DeleteHi Piyush,

DeleteThanks for sharing optimized code with us. I really appreciate your method. But if you don't mind can you please share algorithm for this code because it can be confusing to our readers.

Thanks Rohit for this request.

ReplyDeleteAlgorithm

Step 1: first try to find out the pattern of the required numbers

in this case required numbers are

3,5,6,9,10,12,15,

18,20,21,24,27,30

if you see that the difference between two consecutive numbers are same

in both the rows(for same position)

eg : 5-3 =2, 20-18=2

9-6=3, 24-21=3

this is becuse 15, 30 are common multiplers of 3,5

therefore after 15 , 30 the pattern repeats

step 2 now we can divide each line in two parts or its your wish

I wrote the code by dividing each line.

the pattern of the difference is as(if the starting number is 0 )

3,2,1, 3,1,2,3

first 3 is for 3-0, 18-15...

so i divided row into two parts

1st part: 3,2,1

2nd part: 3,1,2,3

step 3: try to write the code for the above

1st part of the row will be represented by i=1, and 2nd by i=0

we have to take required sum upto n(n=1000 in this case) starting from 0

i)as you can see above that first differnce is same so it will be common

if(num+3<1000)

sum=sum+num+3

ii) in the second difference for first half it is 2, and other half it is 1

the total differnce from the starting

1st half = 5

2nd half = 4,

if(i==1)

{

if(num+5<1000)

sum=sum+num+5; //first half

}

else if(num+4 <1000)

sum=sum+num+4; // second half.

iii) in the third difference if we check the total difference from the starting it will be 6

which is common in both half of the line

so:

if(num+6<=1000)

sum=sum+num+6;

iv) 4th difference only applicable to 2nd half

and also we have to update the value of n by the correct num

for first half it sould 6 because difference between first(here it will be 0) and last number in this is 6

similarly for this difference will be (15-6=9)

so :

if(i==0){

if(num+9<1000)

sum=sum+num+9;

i=1;

num+=9;

}

else{

i=0;

num+=6;

}

for more details or any doubt please feel free to comment

Thanks