Sunday, August 9, 2015

Getting the sum of all multiples of 3 and 5 before a number n

Hello all, today we are going to look on to a problem that says the total of all the multiples of 3 and 5 before a number n.

Note: Before n

So  if I say take the sum of all numbers before 10 which are the multiples of 3 and 5 then the answer would be: 3,5,6,9 and the answer would be 23 (3+5+6+9).

Before going to the implementation lets go back and make some points:
  1. The multiples of 3 and to make a sum of them would be:
    • 3 + 6 + 9 + 12 + 15 ...... which cuts down to : 3 * (1 + 2 + 3 + 4 + 5 ......). Now if you look at this series it is an Arithmetic Progression or you can say that it is the sum of n natural numbers, multiplied by 3.
    • Now the second part which is quite important to notice is that if I say that you have to add all the multiples of  3 before 10 (excluding 10) then then total numbers to be added is 3 * (1 + 2 + 3), which means that the n-1(since we don't have to include n)(for us ,10-1, 9) is divided by 3 and then we consider it to be the part where we can say that apply the formula of addition of first n natural numbers multiplied by 3.
    • So in total the formula would be 3 * (sum of first (n-1)/3 natural numbers), this part is a bit tricky so please give more attention to it.
  2. Same will be the case of numbers divisible by 5 as well.
  3. One more important thing is that if the n is 16 and we have to add all the multiples of 3 and 5 together then the answer would be:
    (3 + 6 + 9 + 12 +15) + (5 + 10 + 15)
    if you notice the expression the digit 15 is added twice since, 3 & 5 both are the multiples of 15 and so added twice.
  4. Now in order to do correct solution we have to remove the digits those are the multiple of 15(i.e 3*5)
  5. So the case would be like this:
        3 * (sum of first (n-1)/3 natural numbers)
    5 * (sum of first (n-1)/5 natural numbers)
    15 * (sum of first (n-1)/15 natural numbers)
Now lets prepare the code :

public class Solution {
    public static Scanner ins = new Scanner(System.in);
    public static sumOfNNaturalNumbers(int n) {
        return (n*(n+1)/2);
    }
    public static int readInt() {
        int result = ins.nextInt();
        ins.nextLine();
        return result;
    }
    public static int readString() {
        return ins.readLine();
    }
    public static void main(String[] args) {
        int n = readInt();
        int answer = 3 * (n-1)/3 + 5 * (n-1)/5 - 15 * (n-1)/15;
        System.out.println(answer);
    }
}

No comments:

Post a Comment