Smallest Common Multiple - Unwanted oscillating result from while loop

Tell us what’s happening:
Hi everyone,
I have been trying to get Least Common multiple. I have been doing this by sorting and then expanding array between two extreme values. After that I just used the while loop to bring the value to the wanted condition. It works well for until I try higher values - the code returns random values between 726541 - 796605 each time I refresh. Can somebody explain this weird behavior? Thanks


function smallestCommons(arr) {  
  arr = arr.sort((a,b) => a-b);
  console.log(arr);
  console.log(arr[arr.length-1]-arr[0]);
  var arrLay = [];
  for (let i = arr[0]; i<=arr[arr.length-1]; i++){
      arrLay.push(i);
  }
  console.log("arrLay = " +arrLay);

  let mult = arrLay[0];
  while(arrLay.every( (item) => mult% item === 0) === false){
    mult++
  } 
  console.log(mult);
  return mult;
}


smallestCommons([23,18]);

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.103 Safari/537.36 OPR/60.0.3255.109.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple/

it seems that your code is triggering the infinite loop protection because it is taking too long to execute

you need to refactor your code to make it more efficient

1 Like

Okey, Thanks.
Do you know where could I read more about these things, such as capacity and speed?

I don’t know where to reference you, but it is about the number of steps needed, your code raise a variable by one and then do multiple checks on it, that’s that need refactoring.

I remember Khan Academy having something on time complexity but can’t find it

1 Like

I struggled a bit on this one to start - mostly because it was a surprisingly deep challenge that more resembled a project. However I sketched abrute force solution in a post yesterday:

Are you familiar with:

  • Sieve of Eratosthenes for finding prime numbers?

  • Are you familiar with prime factorization?

  • Do you realize that the *prime factorization of each number is unique?

Hopefully these hints at the math behind this problem, and solution, help out.

Ah ha!

There is a simpler efficient algorithm that doesn’t require prime factorization of the input range.

  1. Write a Greatest Common Divisor function GCD(a,b).
  2. Note that the Smallest Common Multiple (SCM) of any two numbers a and b is the value: a * b / GCD(a,b).
  3. Calculate the SCM for the first two numbers of the range; then successively calculate the SCM for that value plus the next value in the range until you hit the end of the range.

This is far more efficient than a simple integer loop, yet only 1/2 or 1/3 as much code as my earlier prime-factorization algorithm.

1 Like