Smallest Common Multiple Troubles

JavaScript
1

Tell us what’s happening:

I’m getting the correct answer when I run my code in nodejs but the last test case is failing in FCC editor. Am I missing something?

Your code so far


function smallestCommons(arr) {
  arr = arr.sort((a,b) => a - b)
  arr = Array(arr[1] - arr[0] + 1).fill(arr[0]).map((x,y) => x + y)
  let lcm = 2
  let isLCM = false
  while(!isLCM) {
    if(arr.every(num => lcm % num === 0)) {
      isLCM = true
      break;
    }
    lcm++
  }
  return lcm
}

smallestCommons([23,18]);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/75.0.3770.142 Safari/537.36.

Link to the challenge:

2

If you’re checking each and every possibly number starting from 2, then the loop will have to go on for hundreds of thousands of times (if the lcm is 360 360, for example). After a certain amount of time, the computer will automatically stop looping. Hence, if the lcm isn’t too big, this computer can handle it, but if lcm is huge number, the computer will give up.

1 Like
3

Ahh so basically the FCC test timed out when running my solution up to a large number?

4

Yeah, I had the same problem. Computer just won’t do 360 360 loops. It cuts out after a certain amount of time. You’ll have to reduce the number of loops by checking in multiples of the product of the two biggest numbers in your array (as suggested in the hints).

I’m not sure why this works mathematically. Intuitively, it makes sense, but it assumes that the LCM will always be divisible by the product of the two biggest numbers, plus a third a number. Again, that makes sense, but I don’t like accepting things based on “it makes intuitive sense”. I’d like to see some math proof.

1 Like
5

Yea, I wish I understood the math behind that. Learning programming at a later age and not using math for so long has really exposed how weak my math skills have become.

Anyways, thank you for the help! I got the problem solved by checking in multiples of the product of the two array elements given as arguments and it passed. I’m sure that checking from the two highest numbers in the range would have been much more efficient but I didn’t know that would work mathematically.

1 Like