Least Common Multiple - for loop breaks down - javascript

Question

I'm taking a course on FreeCodeCamp.org and the assignment is to find "Smallest Common Multiple". So I came up with a solution I think works and I does up to a certain point. Then the code just seems like it's breaking down. Here is my code:

function smallestCommons(arr) {
  arr = arr.sort((a,b) => {return a - b;});
  console.log(arr);
  var truesec = false;
  for(var a = arr[1]; truesec != true; a++){

    for(var e = 1; e <= arr[1]; e++){
      //console.log(a % e + " " + e);
      if(a % e != 0){
        truesec = false;
        break;
      }else{
        truesec = true;
      }
    }
    //console.log(truesec + " " + a);
    if(truesec == true){
      return a;
    }
  }

  return a;
}


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

This should return 6056820 according to their checklist but every time I check I get a different result I've gotten both 114461 & 122841 from the same code. Can somebody please tell me what is wrong with this?

Here is the assignment if it helps: Intermediate Algorithm Scripting: Smallest Common Multiple

Answer 1

I would take a different approach to this problem:

1. create function to get all prime factors
2. create array of prime factor of all number between a[0] and a[1]
3. reduce the array as the biggest power for each prime factor.
4. multiple all the prime factor left in the array

Your approach will take O(k*a[1]) when k is the answer - and k can be very high... This approach will take O((a[1])^2)

Consider the following code:

function smallestCommons2(arr) {
    arr.sort((a,b) => {return a - b;});
    let factors = [];
    for(let i = arr[0]; i <= arr[1]; i++)
        factors.push(findPrimeFactors(i));

    let reduced = reduceFactors(factors);
    let ans = 1;
    for (let i in reduced)
        ans *= Math.pow(i, reduced[i]);
    return ans;
}

function reduceFactors(factorsArr) {
    let factorObject = {};
    for (let i in factorsArr) {
        for(let key in factorsArr[i]) {
            if (!(key in factorObject) || factorObject[key] < factorsArr[i][key])
                factorObject[key] = factorsArr[i][key];
        }
    }
    return factorObject;
}

function findPrimeFactors (num) {
    var primeFactors = [];
    while (num % 2 === 0) {
        primeFactors.push(2);
        num = num / 2;
    }

    var sqrtNum = Math.sqrt(num);
    for (var i = 3; i <= sqrtNum; i++) {
        while (num % i === 0) {
            primeFactors.push(i);
            num = num / i;
        }
    }
    if (num > 2)
        primeFactors.push(num);

    let factorObject = {};

    for (let item of primeFactors) {
        if (item in factorObject)
            factorObject[item] += 1;
        else factorObject[item] = 1;
    }
    return factorObject;
}


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

This code will output 6056820 in sec

Edited - found a post that do the same thing in a better way