JS Smallest Common Multiple - Works on VS Code but not on FCC

JavaScript
1

Here is my brute force solution to the JavaScript Smallest Common Multiple challenge.

function smallestCommons(arr) {    

    let check_multiples = (all_multiples) => {
        let node = all_multiples[0];
        let item = node[node.length - 1];  //  The item we are looking for in this iteration, only need to test last item from first array
        let found_this_iter = [];  // Have we found the item, one entry per additional array in all_multiples.
        //  Iterate over all but first arrays
        for (let sa_index = 1; sa_index < all_multiples.length; sa_index++) {
            // Is item in current array?
             if (all_multiples[sa_index].includes(item)) {  // Yes it is
                found_this_iter.push(true);
            } else {
                found_this_iter.push(false);
                break;
            }
        }
        //  Check to see if scm is found
        if (found_this_iter.every(function(item) { return item } )) { return true };  // Returns true if scm found
        return false;  // No scm found
    }

    let power = 1;  // Power we will multiply by
    let found = false;  // Flag indicating if smallest common multiplier has been fund
    let first =  true;  // Flag indicating if this is first iteration, used to initialise array.
    let multiples = [];  //  2D array containing the multiples we have found to date.

    let rangeArr = [];  // Generate a range from the input values
    let min = Math.min(...arr);
    let max = Math.max(...arr);
    for (let i = min; i <= max; i++) { rangeArr.push(i) }

    while (!found) {
        for (let i = 0; i < rangeArr.length; i++) {  // Generate a new multiple for each value passed into the function
            if (first) { multiples[i] = [] };0
            multiples[i].push(rangeArr[i] * power);
        }
        if (first) { first = false };
        found = check_multiples(multiples);  // Check to see if we have found the smallest common multiplier
        if (found) {  // Smallest common multiplier found
            return multiples[0][multiples[0].length-1];
        }
        power++;
    }
  }

  smallestCommons([1,5]);  // 60
  smallestCommons([2, 10]);  // 2520
  smallestCommons([1, 13]);  // 360360

This works when I run it on VS Code, however this isn’t the most efficient of solutions and it takes 140 seconds to execute the above. Probably for this reason the [1,13] and [23,18] tests fail when I run them on the FCC page with the above solution.

If you have any hints or tips on optimising this solution, or ideas for a better approach, they would be much appreciated.

Thanks,
Craig.

2

Fo this one, I’d look up the wikipedia article on finding the least common multiple. There is an algorithm in there, along with the algorithm for finding the gcd, that will greatly speed things up.

2 Likes
3

Hi @JeremyLT

Done, I implemented the simple algorithm from the wikipedia page.

function smallestCommons(arr) {

    let Range = (a, b) => {
        let localArr = [];
        for (let i = min; i <= max; i++) {
            localArr.push(i);
        }
        return localArr;
    }

    function IndexOfLowestValue(localArr) {  // Returns index of the last item in array with the lowest value of array.
        const arrMin = Math.min(...localArr);
        let index = 0;
        for (let i = 0; i < localArr.length; i++) {
            if (localArr[i] == arrMin) {
                index = i;
            }
        }
        return index;
    }

    const allEqual = (arr) => {
        return arr.every(v => v === arr[0]);
    };

    let min = Math.min(...arr);
    let max = Math.max(...arr);
    let allNums = Range(min, max);
    let allOriginals = Array.from(allNums);
    let found = false;
    let retVal = 0;    

    while (!found) {
        let indexLowestVal = IndexOfLowestValue(allNums);
        allNums[indexLowestVal] += allOriginals[indexLowestVal];
        if (allEqual(allNums)) {
            found = true;
            retVal = allNums[0];
        }
    }
    console.log(`retVal is ${retVal}`);
    return retVal;
}

Many thanks for the tip.
Craig.