Smallest Common Multiple, where did I go wrong?

Smallest Common Multiple, where did I go wrong?
0

#1

Tell us what’s happening:
hey all, wannabe coder here. I am having an issue with this algorithm and I can tseem to find out why!!! it passes the first 4 tests, but fails the last 2. Here is some “pseudocode” that will maybe help you guys see what I am doing.

smallestCommon first takes the argument, lets say for example [1,5]. First thing I do is sort the array, just to make sure the lower number is first in the array. That way, if the argument is [5,1], the array gets sorted to [1,5] before any code is executed. After this, I make a newArray filled with all numbers from arr[0] to arr[1]. In this example, it would be [1,2,3,4,5].
Then I take the last digit of the newArray and set it equal to a variable called num. I than pass newArray and num into a new function called divisibleByAll, where num is divided by all numbers in newArray. If at any point one of the numbers in the array does not divide evenly by the variable num, I return false, add 1 to num, and call divisibleByAll again until it returns true. But there is either a bug in my code or a flaw in my logic.

Also, yes I know this is not the best way to do this, and I know a separate array and separate function are not necessary, but I want to get the code working before I start to make it more simple. Any and all help is appreciated :slight_smile:

Your code so far


//this code works for [1,5], [5,1], and [2,10], but fails with [1,13] and [23, 18]

function divisibleByAll (array, num){
  for(let digits in array){
    if (num % array[Number(digits)]!==0){
      return false;
    } //this funtion takes a number, and checks to see if the number is divisible by ALL numbers in newArr(which has all numbers from arr[0] to arr[1]). If not, return false. 
  }
  return true;
}


function smallestCommons(arr) {
  arr = arr.sort(function(a,b){return a-b}); //sort the 2 numbers, so smaller is first
  let newArr = [];
  for (let i = arr[0]; i < arr[1]+1; i++ ){
    newArr.push(i);// make new array filled with all #'s from arr[0] to arr[1] including arr[1]
  }
  
  let num = newArr[newArr.length -1]; //set the last number of the array to a variable. This is the number I am going to start with

  while(divisibleByAll(newArr, num) != true){
    num= num+1;
    divisibleByAll(newArr, num);

  } //this cycles though all number between arr[0] and arr[1] and checks if num is divisble by all of those numbers. If not, number +1, rinse and repeat until divisibleByAll returns true. then, return num. 

  return num;
}


console.log(smallestCommons([1,5]));

Your browser information:

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

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple


#2

The main issue you are not passing the last two tests, is because your solution runs so slow, that it triggers test suite’s infinite loop protection. The tests think you have an infinite loop (which you do not), because it takes so long.

You need to a much more efficient algorithm. One of the parts of your code which is killing the performance is the following while loop:

  while(divisibleByAll(newArr, num) != true){
    num= num+1;
    divisibleByAll(newArr, num);
  }

You are calling divisibleByAll twice for each iteration of the while loop. That is a lot of iterations considering the for loop inside divisibleByAll gets longer each time you add a value to newArr.


#3

While I am happy that my code does, in theory, work, I am sad to hear that I wrote code so inefficient that it triggers infinite loop protection :expressionless:. How many loops does it take for this to trigger?

Alright, well I think I can work with this. I think I’m going to just whip out a notebook and start this one over. Thanks for your help :slight_smile:


#4

It is not the number of loops, but it has to complete in less than 100 milliseconds. All the FCC challenges can be solved in less than 100ms if an efficient algorithm is used.