Javascript for loop giving infinite loop error while calculating LCM

Question

The problem I'm trying to solve is to calculate least common multiple of a given range of numbers. The numbers supplied in the array can be in any order, but the attay will only have two numbers.

My code works for pairs [1,5] , [1,10],[1,12], but once I try [1,13] i'm getting infinite loop error and answer is becoming undefined.

For below code , expected answer is 360360

function smallestCommons(arr) {

  var a     = arr[0];
  var b     = arr[1];
  var start = 0;
  var end   = 0;
 
  if (a<b) {
    start=a;
    end=b;
  }
  else {
    start=b;
    end=a;
  }

  //console.log("Start:"+start);
  //console.log("End:"+end);

  var numArray = [];
  for(let i=start; i<end+1; i++) {
    numArray.push(i);
  }

  console.log(numArray);
  
  var oddArray = [];
  var product  = numArray.reduce((a,b)=>a=a*b);
  
  console.log("Product:"+product);
  console.log(numArray[0]);
  
  var result = 0;
  
  console.log(result);

  //let j=numArray[0];

  for(let j=numArray[0];j<=product;j++) {
    var count = 0;
    for(let k=0;k<numArray.length; k++) {
  
      if(j%numArray[k]==0) {
        count++;
      }
    }
    if(count==numArray.length) {
      return j;
    }
  }
}

console.log(smallestCommons([1,13]));

Answer 1

Your approach is wrong.

What is the LCM of 1, 2, 3, 4? It is 12 because it is 3 x 4.

What your code will do:

var product  = numArray.reduce((a,b)=>a=a*b); // product will be 24
...
for(let j=numArray[0];j<=product;j++) { // iterate from 1 -> 24
    var count = 0;
    for(let k=0;k<numArray.length; k++) { // iterate from 0 -> 3
  
      if(j%numArray[k]==0) { // consider it a hit if j is divisible by an element
        count++;
      }
    }
    if(count==numArray.length) { // on the 4th "hit"
      return j; // return j which is a number between 1 -> 24
    }
  }

If you are running into an infinite loop, it's because you don't get the right number of hits.

The correct approach to an LCM question is to think about prime factors. Let's use 1, 2, 3, 4 again.

For each number, I get a count of prime factors.

1 -> 1(1)
2 -> 2(1), 1(1)
3 -> 3(1), 1(1)
4 -> 2(2), 1(1)

We reduce this set by using max(cnt) for each prime factor. The max count of 1 is 1. The max count of 2 is 2. The max count of 3 is 1. So we then go: 2 x 2 x 3 = 12, and that is our answer.

This requires 2 passes:

1. first pass over the numbers array.
2. second pass over the prime count map.