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

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;
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[multiples.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.

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

``````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);
};

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;
}
}
console.log(`retVal is \${retVal}`);
return retVal;
}
``````

Many thanks for the tip.
Craig.