Smallest Common Multiple passing all but the final test

Smallest Common Multiple passing all but the final test
0.0 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!