Completely stuck on Smallest Common Multiple

Completely stuck on Smallest Common Multiple
0

#1

Hi Campers!

I got completely stuck on Smallest Common Multiple challenge.
Can you give my any tips to get started?

Thank you,
Kuba


#2

Do you understand what your function must do?

If so, then have you tried to write out an algorithm in plain language that will outline the basic steps your function will need to do to arrive a correct result?


#3

I think I just don’t understand the algorithm. Translating it later into Javascript shouldn’t be the problem.


#4

First, I would make sure you understand how you would manually figure out the smallest common multiple for only two numbers. There are a series of steps you would actually take on paper to arrive at the number. Once you can do that, then think about you could apply those same steps to a range of numbers. This challenge can be broken down into smaller problems, each with their own algorithm that you put together in the end.

You can search google for “least common multiple” algorithms and you will find there are many different ways to calculate it.

See if you can break it down into the smallest steps and write them out on paper or type them up. Feel free to post your attempt at an algorithm so we can guide and direct you to finding one which you understand and will be able to code.


#5

Here’s what I created as you suggested - Smallest common multiple for two numbers.
But how to make it working for array of numbers :roll_eyes:

function LCMforTwo(a,b){
var lcm = Math.abs(a * b) / gcd(a,b);
function gcd(a,b){
while (b != 0){
      c = a % b;
      a = b;
      b = c;
    }
 return a;
}
return lcm;
console.log(lcm);
}
LCMforTwo(6541,498);

#6

If you want to find the lcm of a list of numbers (1, 2, 3, 4, 5), then you could first find the lcm of the first two numbers (lcm(1,2) = 2) and then find the lcm of this result and the third number (lcm(2, 3) = 6), then find the lcm of this result and the 4th number (lcm(6, 4) = 12, and finally find the lcm of this result and the last number (lcm(12, 5) = 60).

Knowing the above steps can be taken, you now must figure out how to create the list of numbers from two numbers and then iterate through this list taking the lcm of the applicable pairs. I see a excellent situation to use the reduce function here.


#7

Hooray! Thank you so much for help :smile:
This is my final code. Gosh, that was really hard.

function smallestCommons(arr){
var min = Math.min(arr[0],arr[1]);
var max = Math.max(arr[0],arr[1]);

var range = [];
for(var i = min; i <= max; i++){
  range.push(i);
}

var lcm = range[0];
for(var j = 1; j < range.length; j++){
  lcm = (lcm * range[j]) / gcd(lcm, range[j]);
}
return lcm;

 function gcd(a,b){
  while (b != 0){
      c = a % b;
      a = b;
      b = c;
    }
 return a;
 }
}

#8

I am also stuck, and, before resorting to solving the problem using the solution that has been so generously offered here, I wanted to still share my code here and ask what is wrong (well, even if everything is, I would still like to ask for some help :slight_smile:)

my solution was:
function smallestCommons(arr) {
var newArr = [];
arr.sort(function(a,b){
return a-b
});
for (var i=arr[0]; i<=arr[(arr.length-1)]; i++) {
newArr.push(i);
}
for (var counter=1; counter>newArr[(newArr.length-1)]; counter++){
for (var j=0; j<newArr.length; j++) {
if (counter%arr[j]!==0) break;
}
}
return counter;
}

what I am doing is:

  1. Sorting the initial pair in ascending order.
  2. Creating a new array and pushing the range between the given two number, including the numbers, into the array.
  3. Initializing a counter, potential smallest common multiple, and iterating through the range in my array, trying to see if there is at least ONE number in the range that counter cannot be divided by. If, indeed, counter does not divide evenly by at least one element of the array, I use break statement.
  4. Counter increments, and we are looking again.

I have a feeling when I have an if-break statement I am still doing everything right, but then I just have no idea what to do further. In the meanwhile I will try to use the standard solution with dividing the a*b by the greatest common divisor. Thank you in advance, any help is appreciated!