CODEWITHSUNDEEP
javascriptoptimization
an_bozh
an_bozh

Reputation: 63

find sum of multiples 3 and 5, JS

I'm given a number and I need to find the sum of the multiples of 3 and 5 below the number. For example: 20 => 78 = 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18

My code works, but not for numbers greater than 1,000,000 (I tested it for 100,000 - it gives the result with 2sec delay). So, it should be optimized. Could someone help me? Why is my code slow? Thanks.

My logic is as follows:

my code:

  function sumOfMultiples(number) {

    let numberBelow = number - 1;  
    let numberOfThrees = Math.floor(numberBelow / 3);
    let numberOfFives = Math.floor(numberBelow / 5);  
    let multiples = [];
    let multipleOfThree = 0;
    let multipleOfFive = 0;

    for (var i = 0; i < numberOfThrees; i++) {
      multiples.push(multipleOfThree += 3);
    }

    for (var j = 0; j < numberOfFives; j++) {
      multiples.push(multipleOfFive += 5);
    }

    return multiples
              .filter((item, index) => multiples.indexOf(item) === index)
              .reduce((a, b) => a + b);    
 }

Upvotes: -1

Views: 2057

Answers (5)

Abito Prakash
Abito Prakash

Reputation: 4770

You can also do this without using any loops.

For example if N is 1000, the sum of all multiples of 3 under 1000 is 3 + 6 + 9 ..... 999 => 3( 1 + 2 + 3 .... 333)

Similarly for 5, sum is 5(1 + 2 + 3 .... 200). But we have to subtract common multiples like 15, 30, 45 (multiples of 15)

And sum of first N natural numbers is N*(N+1)/2;

Putting all of this together

// Returns sum of first N natural numbers
const sumN = (N) => (N * (N + 1)) / 2;

// Returns number of multiples of a below N
const noOfMulitples = (N, a) => Math.floor((N - 1) / a);

function sumOfMulitples(N) {
    const n3 = noOfMulitples(N, 3); // Number of multiples of 3 under N
    const n5 = noOfMulitples(N, 5); // Number of multiples of 5 under N
    const n15 = noOfMulitples(N, 15); // Number of multiples of 3 & 5 under N

    return 3 * sumN(n3) + 5 * sumN(n5) - 15 * sumN(n15);
}

Upvotes: 3

Ivansito87
Ivansito87

Reputation: 39

you can do something like this

function multiplesOfFiveAndThree(){
 let sum = 0;
  for(let i = 1; i < 1000; i++) {
    if (i % 3 === 0 || i % 5 === 0) sum += i;
  }
  return sum;
}

console.log(multiplesOfFiveAndThree());

Upvotes: 0

Code Maniac
Code Maniac

Reputation: 37755

You can do something like this

  • Set the difference equal to 5 - 3
  • Start loop with current as 0, keep looping until current is less than number,
  • Add 3 to current in every iteration,
  • Add difference to current and check if it is divisible by 5 only and less than number, than add it final result,
  • Add current to final result

function sumOfMultiples(number) {
    let num = 0;
    let difference  = 5 - 3
    let current = 0
    while(current < number){
      current += 3
      let temp = current + difference
      if((temp % 5 === 0) && (temp %3 !== 0) && temp < number ){
        num += temp
      }
      difference += 2
      if(current < number){
        num += current
      }
    }
   return num
}
 
console.log(sumOfMultiples(20))
console.log(sumOfMultiples(1000));
console.log(sumOfMultiples(100000));
console.log(sumOfMultiples(10000000));

Upvotes: 0

Maheer Ali
Maheer Ali

Reputation: 36584

You can do that just using a single loop.

function sumOfMultiples(number) {
    let sum = 0;
    for(let i = 1; i < number; i++){
       if(i % 3 === 0 || i % 5 === 0){
        sum += i;
       }
    }   
    return sum;
 }
 
 console.time('t');
 console.log(sumOfMultiples(100000))
 console.timeEnd('t')

Upvotes: 1

Djaouad
Djaouad

Reputation: 22776

You can just run a loop from 1 to number, and use the modulo operator % to check if i divides 3 or 5:

function sumOfMultiples(number) {
  var result = 0;
  
  for (var i = 0; i < number; i++) {
    if (i % 5 == 0 || i % 3 == 0) {
      result += i;
    }
  }

  return result;
}

console.log(sumOfMultiples(1000));
console.log(sumOfMultiples(100000));
console.log(sumOfMultiples(10000000));

Upvotes: 1

Related Questions