Intermediate Algorithms and Data Structures: Smallest Common Multiple

I have somewhat of a solution, but it causes the fCC console to tell me that there is an infinite loop, when eventually in the Chrome Dev console it gives me the solutions that the tests would ask for. I understand that I haven’t checked to see if everything divides evenly, I have an idea of how to fix that. However overall I am unsure of what to change at this point, it feels like I have tunnel vision and can’t see other possible ways to form a solution. When you have tunnel vision, how do you snap out of it? Would it help to go through the entire JavaScript Algorithms and Data Structures course again? Please let me know of your methods, or if you have any suggestions with changing what I have so far, please let me know! Below is my code:

function smallestCommons(arr) {
    let low = arr[0];
    let high = arr[1];
    if (arr[0] < arr[1]) {
      low = arr[0];
      high = arr[1];
    } else {
      high = arr[0];
      low = arr[1];
    }
    let incrementArr = [];
    for (let i = low; i <= high; i++) {
      incrementArr.push([i]);
    }
    let lastOfFirstArr = incrementArr[0][incrementArr[0].length - 1]
    let truth = [];
    let foundLCM = false;
    while (foundLCM === false) {
      for (let i = 1; i < incrementArr.length; i++) {
          let truthFragment = incrementArr[i].some(elem => {
            if (incrementArr[0][incrementArr[0].length - 1] === elem) {
              return true;
            } else {
              return false;
            }
          })
          truth.push(truthFragment);
          truthFragment = false;
      }
      foundLCM = truth.every(fragment => {
        if (fragment === true) {
          return true;
        } else {
          return false;
        }
      })
      truth = [];
      if (foundLCM === false) {
        for (let plus = 0; plus < incrementArr.length; plus++) {
          incrementArr[plus].push(incrementArr[plus][incrementArr[plus].length - 1] + incrementArr[plus][0]);
        }
      } else {
        console.log(incrementArr[0][incrementArr[0].length - 1])
        return incrementArr[0][incrementArr[0].length - 1];
      }
    }
  }

The further I get to the end of the course the more challenging and frustrating it becomes. I hope to use any problem-solving tips and tricks that you may have as I go forward. Thank you!

Solving problems like this is not so much about writing the code itself but rather about understanding how to solve the problem. Can you explain to us in plain language what you are attempting to do here? In other words, explain how your algorithm works in words, not code.

No problem, I will edit my post.

No need to edit your original post. We would want to see your code too. I’m just asking you to explain your code in plain language as well. Or actually, explain what you want your code to do :slightly_smiling_face:

Here is the code with comments, please let me know if there is a part that you have questions about. Thank you!

function smallestCommons(arr) {
    // Set low and high limits for creating the incrementArr array.
    let low = arr[0];
    let high = arr[1];
    // This is to sort out the high and low because it's easier to work in one direction of iteration.
    if (arr[0] < arr[1]) {
      low = arr[0];
      high = arr[1];
    } else {
      high = arr[0];
      low = arr[1];
    }
    // Now adding the start, the numbers in between and the end limits 
    // to the incrementArr as their own separate arrays to be compared.
    let incrementArr = [];
    for (let i = low; i <= high; i++) {
      incrementArr.push([i]);
    }
   // This is the result after filling out the incrementArr:
   // [ [1], [2], [3], [4], [5] ]

    // The truth array will keep track of any true/false returned when comparing 
    // the last value of the first nested array inside of incrementArr to each element 
    // in the other nested arrays inside of incrementArr.
    let truth = [];
    let foundLCM = false;
    while (foundLCM === false) {
      for (let i = 1; i < incrementArr.length; i++) {
          let truthFragment = incrementArr[i].some(elem => {

            // For some reason, the console did not like 
            // when I used [-1] instead of [incrementArr[0].length - 1].

            if (incrementArr[0][incrementArr[0].length - 1] === elem) {
              // If there is at least one element (elem) anywhere in each nested array of incrementArr 
              // that matches the highest value of the first nested array, return true.
              // The first array of incrementArr will increment by 1, so then 
             // each number will be compared to its highest value until 
             // the first array reaches a number that every other array in incrementArr has.
              return true;
            } else {
              return false;
            }
          })
          // Whether a matching value was found or not, 
          // it gets added to the truth array.
          truth.push(truthFragment);
          truthFragment = false;
      }
      // foundLCM started out as false, but as soon as every boolean in the 
      // truth array is true, then foundLCM would become true.
      foundLCM = truth.every(fragment => {
        if (fragment === true) {
          return true;
        } else {
          return false;
        }
      })
      // If foundLCM ends up remaining false, 
      // then the truth array needs to be emptied out for the next loop.
      truth = [];

      // If foundLCM is false, then the next highest number for 
      // each nested array in incrementArr will be added.

      // This is the result after going through the while loop once:
      // [ [1, 2], [2, 4], [3, 6], [4, 8], [5, 10] ]
      if (foundLCM === false) {
        for (let plus = 0; plus < incrementArr.length; plus++) {
          incrementArr[plus].push(incrementArr[plus][incrementArr[plus].length - 1] + incrementArr[plus][0]);
        }
      } else {
        // If foundLCM is true, then the smallest common multiple will be returned.
        console.log(incrementArr[0][incrementArr[0].length - 1])
        return incrementArr[0][incrementArr[0].length - 1];
      }
    }
  }

This is closer, and I suppose it is adequate, but what I really wanted was just a plain language description of what you want your algorithm to do. Literally, a list of steps written out in English. Or a few sentences explaining how you will find the solution. But no code at all. Just words.

This may seem like an unnecessary step, but if you can’t explain in plain English how to solve this then you won’t be able to code it correctly. I could explain my solution to you in just a few steps without using one bit of code and I’m pretty sure it would be enough for you to then translate it into JS. So I want you to explain your solution to me so I can translate it into JS.

Sorry I misunderstood, here is an explanation in plain words without the code:

I would like my algorithm to find the smallest common multiple by creating a list of numbers for each number in between the range. Then check each list to find the first number that is found in all lists. If it isn’t found yet, I will keep adding a new higher value to each list of numbers. If I find it, I will return that value.

Please let me know if this explanation needs more added to it.

Would you expand a little more on what this means? How will you determine what numbers will be in each of these lists?

Of course! For every number that there is within a given range, each number will be the starting point of its own list. The starting point will be the first value added to each list, in ascending order from least to greatest. That starting point will also help create the next highest value for that list by using it as the value to increment. All of these lists will be stored in an array.

OK, I think I understand what you are trying to do here. I think you need to refactor your code so it is easier to understand. The following statements sound like they can be turned into functions since you are going to do them over and over again:

“Then check each list to find the first number that is found in all lists.”

“If it isn’t found yet, I will keep adding a new higher value to each list of numbers.”

Breaking these down into separate functions will help make the code more readable and also help you troubleshoot where the problem is.

And I would use better variable names. It is very hard to follow something like:

incrementArr[plus].push(incrementArr[plus][incrementArr[plus].length - 1] + incrementArr[plus][0]);

Even using temporary variables with descriptive names to store some of these values would be an improvement.

I will tell you that there are several solutions to this problem that don’t require you to create any lists of numbers. One of those utilizes a formula for finding the smallest common multiple between two numbers (but it goes by a different name). Another one doesn’t use any fancy formulas, you just need to reason a little bit about what numbers you actually need to test to see if they are divisible by all numbers in the range.

Thank you for giving these suggestions, I am going to make functions out of the statements and fix the temporary variable names.

I’ve decided to just redesign it, since the program will just assume that what I wrote is an infinite loop, even though it isn’t.

First of all it is really good that you made a solution, even though it doesn’t meet all the requirements!

Depending on the input it might as well become an infinite loop, you probably don’t want to run smallestCommons([2, 1000000]) in your browser for weeks :slightly_smiling_face:

fCC limits the time your function runs so the tab won’t freeze. That is also very useful to realize whether your algorithm might be working but not efficient enough.

The next step to your final solution is identifying ways to reduce time complexity (= number of operations) and / or space complexity (that solution there has for each divider an array that has in the worst case a length that is the same as the smallest multiple itself (if 1 is in the range))
In this case, probably even starting with 1 and testing each number for being divisible by the all the desired numbers would have been faster

Another trick is preprocessing:
smallestCommons([2, 10]) and smallestCommons([7, 10]) both have the same result, but the first ends up with 9 arrays having 1260 elements each, the second only 4 arrays with 360 elements each

Find those numbers you don’t need, analyse why you don’t need them and then you could use it to make a new algorithm

I have finally found a solution that is shorter and sweeter!

I read somewhere else on the forums to just start with the largest number in the range. I took that and used an every method to see if each new incremented number was divisible by all the numbers. No infinite loop detected!

Another thing that helped was taking some time away from this challenge to work on other projects that would build up my skills. It felt so counterproductive sitting there and pondering for hours on end what my solution could be. With fresh eyes and new perspectives I immediately found a solution.

Looking back on my original solution, it really does look unreadable. This new solution I made has improved variable naming. In the future, I should read up on how to make code more efficient.

Can I show the better solution here?

Thank you!

Go for it!

Okay, here it is:

function smallestCommons(arr) {

  let newArr = arr.slice();
  let rangeStart;
  let rangeEnd;

  if (newArr[0] < newArr[1]) {
    rangeStart = newArr[0];
    rangeEnd = newArr[1];
  } else {
    rangeStart = newArr[1];
    rangeEnd = newArr[0];
  }

  let moduloArr = [   ];

  for (let i = rangeStart; i < rangeEnd; i++) {
    moduloArr.push(i);
  }

  let smallestCommonMultiple = 0;
  let highestIncrement = 0;
  highestIncrement += rangeEnd;
  smallestCommonMultiple += highestIncrement;

  let isFound = moduloArr.every(modulo => {
    return smallestCommonMultiple % modulo === 0;
  })

  while (!isFound) {
    smallestCommonMultiple += highestIncrement;
    isFound = moduloArr.every(modulo => {
      return smallestCommonMultiple % modulo === 0;
    })
  }

  return smallestCommonMultiple;
}
1 Like

If you like, here are 2 suggestions for your solution:

  1. You can use Math.min and Math.max on an array of numbers by using the spread operator:
    Math.min(...arr)

You don’t change newArr afterwards, so it is unnessessary to copy it in the first place (it makes no big difference here, but the earlier you start thinking about those little things the better it is :grinning: )

is exactly the same as:

A good indicator to make it a function. Just call that function in the loop like:
while (!isFound())
That makes your loop cleaner because then the only line inside is the important change of smallestCommonMultiple