Smallest Common Multiple - Stuck at last test

JavaScript
1

Hi everyone :slight_smile:

So I’ve been doing the Intermediate Algorithm Scripting: Smallest Common Multiple and I almost got it. I’m passing all tests except the last one. I think the problem is that the code I wrote gives me a potential infinite loop message, which might be stopping it before it actually reaches the solution of the last test …? Since it is a very large number.

I’ve looked at other threads about the same problem but could find a solution :confused: Everyone was saying to make the algorithm less “brute-force” but I can’t figure out a good way to do it.

So how can I refine this code so that I don’t get this error anymore? I know that it’s not very elegant but it’s the only way I could think of to make it work. I kinda suck at math problems like these :sweat_smile:

Thanks in advance and have a nice day!
Happy coding

Your code so far


function smallestCommons(arr) {
let num = 1, i = 1;
let foundSolution = false;
let extArray = arr[0] < arr[1] ? Array.from({length: arr[1] - arr[0] + 1}, (a, b) => arr[0] + b) : Array.from({length: arr[0]-arr[1] + 1}, (a, b) => arr[0] - b);

while(foundSolution == false) {
  let counter = 0;
  for(i in extArray) {
    if(num % extArray[i] === 0) {
      counter++;
    }
    if(counter >= extArray.length) {
      foundSolution = true;
      return num;
    }
  }
  num++;
}
}



console.log(smallestCommons([23,18]));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/80.0.3987.122 Safari/537.36.

Challenge: Smallest Common Multiple

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

2

to make it less brute force you can do a bit of research on algorithms about finding Smallest Common Multiple

a few things:
a number is prime if it is divisible only by 1 and itself - so you would check if it has divisors, but you can stop checking at its square root - the first divisor is at most the square root

A common algorithm is:

  • find greatest common divisor
  • multiply numbers in the range
  • divide result by gcd, this is the Smallest Common Divisor

My solution was

  • find all primes below the highest number in the range
  • multiply all the numbers in the range
  • for each prime number: divide the result by the prime number multiple times, stop at last number that is still divisible from all the numbers in the range