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

Seem like is is not breaking but taking a lot of time... I believe you should re-think your algorithm - this is VERY heavy brute force... — dWinder, Dec 30 '18 at 15:08
I would suggest to calculate the gcd (greatest common devider) of a and b (gcd(a,b)). For this you just should check out an implementation of the Euclidean algorithm (https://en.m.wikipedia.org/wiki/Euclidean_algorithm) Once you can get the lcm ( least/smallest common multiplier) by following division lcm(a,b) = a*b / gcd(a,b) — Andi Kleinbichler, Dec 30 '18 at 15:35
`arr = arr.sort` is unnecessar re-assignment since `sort` changes `arr` already. — connexo, Dec 30 '18 at 15:37

score 3 · Answer 1 · answered Dec 30 '18 at 15:32

What your algorithm trying to do is find the common multiple between 1 and the greater number in the array, which might take a very long time. However, the question from the FreeCodeCamp asks you to find the common multiple between the two numbers in the array, so the result calculated from your algorithm does not match the tests.

To make your solution works, you can change

from for (var e = 1; e <= arr[1]; e++)

to for (var e = arr[0]; e <= arr[1]; e++)

in order to loop between two numbers in the array.

dWinder · Accepted Answer · 2018-12-31T11:02:34.490

I would take a different approach to this problem:

create function to get all prime factors
create array of prime factor of all number between a[0] and a[1]
reduce the array as the biggest power for each prime factor.
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

This surely works but it's a bit more advanced then what I can understand yet. Anyways thanks for the help. — Nikcio, Dec 30 '18 at 21:35

Least Common Multiple - for loop breaks down - javascript

2 Answers2