Smallest Common Multiple -- Timeout error

Smallest Common Multiple -- Timeout error
0

#1

I’m having an issue with the smallest common multiple challenge. I’d assume that my algorithm needs refactoring because when I run the tests only the last one fails. When I run it on codepen, I get told I have an infinite (or extremely long running) loop. My best guess is that my algorithm is extremely inefficient and is timing out before it calculates the multiple. See my code below:

function smallestCommons(arr) {
  arr = arr.sort();
  if (arr.length > 2) {
    return "Incorrect array size";
  }
  var count = arr[0] * arr[0];
  var check = false;
  var num = 0;
  do {
    var test = false;
    for (var i = arr[0]; i <= arr[1]; i++) {
      if (count % i === 0) {
        test = true;
      } else {
        test = false;
        break;
      }
    }
    if (test) {
      check = true;
      num = count;
    }
    count++;
  } while (!check);
  return num;
}


smallestCommons([23, 18]) 

Any help would be appreciated.


#2

My gues is that the problem lies in the way you define count. Let’s say arr[0] is 1, and arr[1] is 5, then it would have to find something that is divisible by 1, 2, 3, 4 and 5. In your code above you start count then at 1 (1 * 1) and go through the loop over and over until it reaches the correct number, each time increasing by 1. If it has to find a large number (let’s say 10.000) then it would have to do 10.000 iterations.

I imagine that codepen has a sort of filter where after the n’th iteration it considers to be stuck in an infinite loop and cancels the whole proces.

What you can do to improve this, is first to initialize count as arr[0] * arr[1], since the final result will be some multiple of this. If you then also add a new variable which holds the factor (so the multiple of your count variable). You can then start checking if count * factor is divisible by all your numbers. If test becomes false, you then increase factor by 1 and repeat. You can then start iterating, but over a much smaller set of numbers.


function smallestCommons(arr) {
  arr = arr.sort();
  if (arr.length > 2) {
    return "Incorrect array size";
  }
  var count = arr[0] * arr[1];
  var check = false;
  var factor = 1;
  do {
    var test = true;
    var num = count * factor;
    for (var i = arr[0]; i <= arr[1]; i++) {
      if (num % i !== 0) {
        test = false;
        break;
      }
    }
    if (test) {
      check = true;
    }
    factor++;
  } while (!check);
  return num;
}


smallestCommons([1,5]);

#3

Perfect. Thank you for your help. I was slightly confused at first about how you managed to return num from outside the do...while loop, until i remembered JavaScripts odd behaviour with regards to “variable hoisting”. I’m sure that there is a more mathematically efficient method for determining SCM, but I’ll revisit that in the future. Thanks again!