# Smallest Common Multiple passing all but the final test

Smallest Common Multiple passing all but the final test
0

#1

I think my code is logically correct but maybe too brutish.
My first guess is that it’s timing out on the last set with the larger numbers… but then I saw that many others have had the same problem. I’ve looked through the problems other people were having and still don’t see my error. Any help would be appreciated.

Thanks

``````function smallestCommons(arr) {
// functional sort arr into an array called order
let order = arr[0] > arr[1] ? [arr[1],arr[0]] : [...arr];
// declare an empty array to hold the subset
let subSet = [];
// while loop condition
let found = false;
// add range of numbers to subset (includes origial low number)
for ( let n=order[0]; n<order[1]; n++ ) {
subSet.push(n);
}
// multiplier
let i=1;
while(!found){
let count = 0;
// multiply original high number by iteration
let num = i*order[1];
// loop through subset and count the number of even divisions...
// multiplying by order[1] means we don't have to check the high number
for ( let j=subSet[0]; j<order[1]; j++ ) {
if ( num % j === 0 ){
count++;
}
}
// if we find a num value that returns and even division for everything in the subset, break the loop and return the number, else itterate the multiplier...
if ( count === subSet.length ){
found = true;
return num;
}else{
i++;
}
}
}
``````

#2

It works for me in codepen so I think the test is timing out. You need a more efficient algorithm. I’ll see if I can take a closer look later.

#3

It must be timing out.

Your algorithm is checking every multiple of the largest number as a possible LCM for the entire range. That does work but with larger range or larger numbers that becomes less efficient resulting in a lot of iterations.

This is what I did. This may not be the most efficient but I was satisfied with the results for the challenge. Not an algorithm but a walk-through of my logic. Peek or not - hope this helps.

In the case of [1,5]
LCM of 4 and 5 try 5 - no, try 10 - no, 15 - no, 20 - YES!
LCM of 4 and 5 is 20 so any LCM for range must be a mult of 20 so only check multiples of 20 going forward
LCM of 20 and 3 try 20 - no, try 40 - no, try 60 - yes
LCM of 20 and 3 is 60 so LCM for range must be mult of 60 so only check multiples of 60
LCM of 60 and 2 is 60
LCM of 60 and 1 is 60

You could probably shave a few iterations off knowing that LCM of any two consecutive number will be n * (n+1) or in this case 4 * 5 = 20. I didn’t bother.

There are probably more improvements that could determine at what point you could quit looking (like where LCM becomes 60 and doesn’t change thereafter). I didn’t bother with that either.

#4

I like that Idea! Thank you for the detailed reply, and I appreciate that you offered the idea rather than the code. I will try to implement it and report back!

#5

Took me a couple of days to get back to it because I was busy with other work stuff, but this is the passing code I came up with:

``````function smallestCommons(arr) {
let order = arr[0] > arr[1] ? [arr[1],arr[0]] : [...arr];
let subSet = [];

for ( let n=order[0]; n<order[1]; n++ ) {
subSet.push(n);
}

let num = subSet[subSet.length-1] * order[1];

for ( var i=subSet.length-2; i>=0; i--) {
if ( num % subSet[i] !== 0) {
let next = true;
for (let j=2; next; j++ ){
let tempNum = num * j;
if ( tempNum % subSet[i] === 0 ){
num = tempNum;
next = false;
}
}
}
}
return num;
}
``````

I used the n*(n+1) idea to set the initial number and then used length-2 to minimize iterations since i didn’t need to check n or n+1 at that point, but in any case your idea of reseting the LCM during the iteration makes all the difference!

#6

Awesome! Blazing fast - good work!