Arithmetic Progression

Q:-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.
  
Method 1 (Brute force Method) :
the simple way to solve the above question by using simply modulus operator and running the loop till 1000 like as follows :

     for(int i=1;i<1000;i++)
        {
            if(i%3==0 || i%5==0)
            {
            result=result+i;    
            } } 

Time Complexity:O(n)

Method 2 (Arithmetic Progression):

Another solution of the above question would be first we find the sum of number divisible by 3 and then we find the sum of numbers divisible by 5 and then subtract from them the sum of number divisible by 15. Note we are subtracting the sum of number divisible by 15 because number which are divisible by 15 are divisible by both 3 and 5 hence we have added them twice.Consequently we will have to subtract them once to get the correct result:
Result=(Sum_of_Number_divisible by_3+Sum_of_Number_divisible by_5)   -Sum_of_Number_divisible by_15

How to find the sum of number divisible by 3 ?
3+6+9+.............999=166833
1. first we will find the largest number less than 1000 divisible by 3 .
2. As we can see the sum of number divisible by 3 is an AP hence we will use Sn=n/2(2a1+(n-1)*d)
where n is the last term and to find the last term we will use the An=A1+(n-1)*d

How to find the largest number less than 1000 divisible by 3?
1. divide 999 by 3 and get the remainder
2. subtract the remainder from the 999 you will get the result.

To find the Sum of numbers divisible by 5 and 15 we will follow the same procedure as above 

Implementation:

public class Arithmetic {
public static void main (String[] args) throws java.lang.Exception
{
float result=0;
//we have taken 999 because we have to find out the sum to less than 1000  
result=SumDivisbleBy(3,999)+SumDivisbleBy(5,999)-SumDivisbleBy(15,999);
System.out.println((int)result);
}
// function to apply arithmetic and finding sum
private static float SumDivisbleBy(int n, int p){
      
float num=largestNum(n,p);
// finding last term using an=a1+(n-1)*d where an is the nth term of AP and a1 is the first term
float last=(num-n)/n+1;
    
/* finding  the sum using Sn=n/2[2*a1+(n-1)*d]  */ 
float result =(2*n)+((last-1)*n)*last/2;
float other=last/2;
result=result*other;
    
return result;
}
//function to find the largest num less than 1000 divisible by n
private static float largestNum(int n, int p) {
int rem=p%n;
p=p-rem;
return p;
}
}
 

Time Complexity : O(1)

Please comment if you find any mistake  in the post.