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.
About Author:
I am simple guy with lot of ambitions. My main motive is to share whatever knowledge I have related to programming. With me you can easily learn how to solve any programming problem in Java.You can connect with me on social networking sites also.
Let's Get Connected: Linkedin | Facebook | Google Plus
Project Euler | Problem 1 | Multiples of 3 or 5
Reviewed by Rohit Agarwal
on
10/23/2016
Rating:
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