Smallest Common Multiple, stuck before I even start

1

I started off not understanding what was even being asked of me, so I went the algorithms wiki entry to look at the hints. This is what I have as a starting point:

function smallestCommons(arr) {
  
  var sortedArr = arr.sort(function(a,b) {
    return a - b;
  }),
      expandedArr = [],
      x = sortedArr[0],
      y = sortedArr[1];
  
  for (var i = y; i >= x; i-- ) {
    expandedArr.push(i);
  }
  return expandedArr;
}


smallestCommons([13,4]);

Now, I think I understand what they are asking, I have read the wiki and the suggested link on the problem page, but I really don’t know how I am supposed to proceed without looking up the answer somewhere else.

2

What do you think they are asking for, in your own words?

I was actually stuck on this for 2 weeks and had to learn some maths on Khan Academy so I could solve the problem by hand (using small inputs) before translating that into an algorithm.

It’s tricky…stick with it :slight_smile:

1 Like
3

First of all - you have 3 variables there (x, y and expandedArr) that you haven’t declared with var keyword.

Second - you don’t really need x and y. You can just refer to sortedArr in your for loop. Something like this:

for (var i = sortedArr[0]; i <= sortedArr[1]; i++){
  expandedArr.push(i)
}

Now, as for the getting the actual smallest common multiple, there is a simple formula to that. Smallest common mulitple of a and b is a*b divided by their greatest common divisor. If you want to get a smallest common multiple of an array of numbers, you just take 2 numbers from the array, get their scm, pair your result with next number in the array, get smc, and so on.

Heres an article on getting the greatest common divisor.

4

I need to find the least common multiple of each item between and including the two parameters, i.e. all of the numbers in the array I’ve created.

I’ve been studying on least common multiples, prime factors, greatest common divisors etc., but I don’t understand how I am supposed to work this out across every number in an array.

5

If your problem is applying the math to each, consecutive element of the array, then there is a built-in function for that, and you must have encountered it on your previous challenges :wink:

6

One thing you can try is use the map() method to loop thru all the elements of your array.
What helped me was first visualize what the array with all the sequential sorted numbers looks like.
I built a function to do that.
Then I built a function to compute the lcm of 2 numbers.
Finally I mapped all the elements of the array to find the overall lcm among all these numbers, not just 2 of them.

For ex. [1, 5] will become [1, 2, 3, 4, 5] once all the sequential numbers are displayed and sorted.
Now I find the lcm between the first two numbers, 1 and 2, which is 2.
At this point I proceed to find the lcm of the array where the first element has become 2, so:
[2, 3, 4, 5]
Now I find the lcm between 2 and 3 which is 6. My array now becomes [6, 4, 5].
lcm of 6 and 4 is 12. So my array has reduced to [12, 5] and lcm between 12 and 5 is 60

My code is probably more complicated than in needs to be but if helps you here it is:

function smallestCommons(arr) {
//Sort the array in ascending order
arr.sort(function(a, b)
{
return a -b;
});
// Make a function to build an array where to store all the sequential numbers
function printAllSequentialNum(min, max)
{
var allSequentialNum = [];

for(var i = min; i <=max; i++)
{
allSequentialNum.push(i);
}
return allSequentialNum;
}

/* One way to solve this problem is by using the Euclid algorithm: LCM = n1 * n2 / GCD
Find the GCD first.*/
function lcm(num1, num2)
{
for(var GCD = num1; GCD>0; GCD–)

  if(num2 % GCD === 0 && num1 % GCD === 0)

  return (num1 * num2) / GCD;//This is the LCM of 2 numbers

}
//map the whole array to find the lcm not just between 2 numbers but among all of them
var multiple = arr[0];
printAllSequentialNum(arr[0], arr[1]).map((num, i) =>
{
multiple = lcm(multiple, num);
console.log(multiple);
});
return multiple;

}

smallestCommons([1,5]);