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 Solution in Java
Project Euler Problem 1

Concept :


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


Java Program :




Output :


Output of Project Euler problem 1 - Multiple of 3 or 5 below 1000 in Java
Output - Project Euler Problem

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 |

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

4 comments:

  1. Hi Rohit,

    I 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);

    }

    }

    ReplyDelete
    Replies
    1. For any doubts and update pls comment...

      Delete
    2. Hi Piyush,

      Thanks 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.

      Delete
  2. Thanks Rohit for this request.

    Algorithm
    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

    ReplyDelete

Please provide your valuable comments. If you have any suggestion please share with me I will work on it and if you have any question or doubt please ask, don't hesitate. I am your friend, i will clarify all your doubts.

Powered by Blogger.