Help WIth Smallest Common Multiple Challenge

1

Hey there, I could use some feedback on this code for Smallest Common Multiple Algorithm Challenge. I am stuck and can’t get any further. I have created a function that will return the LCM for any two numbers for a specified array length. I don’t know how to check to see if any of my multiples are in fact the LCM. Right now I just need some pointers to get me going in the right direction. Thanks for the help.

function smallestCommons(arr) {
  arr = arr.sort(function(a, b){
    return a - b;
  });
  var arrRange = []; 
  var multiArr = []; 
  var min = Math.min(arr[0], arr[1]);
  var max = Math.max(arr[0], arr[1]); 
  var arrA = []; // array created to store all multiples of greatest number to check other LCM's                         against later
  var units = 20; // length that arrA will be. Need better way to find possible LCM's
  
//create all the missing numbers from arr[0] to arr[1];
  for (i = arr[0]; i <= arr[1]; i ++) {
    arrRange.push(i);
  }
  
//input any two numbers and it will return the LCM.
  function lcmArr(a, b) {
    var small;
    for (i = 1; i <= units; i ++) {
      arrA.push(i * a);
    }
    
    for (i = 0; i < arrA.length; i ++) {
      if (arrA[i]%b === 0) {
        multiArr.push(arrA[i]); //creates all the multiples for a, b
      }
    }
    
    small = multiArr.shift(); // grabs the first index, which is the LCM for a, b
    return small;   
    
  }


  
}
smallestCommons([1,5]);
2

Hi, i’m not sure that i understand your code, but i guess that you are trying to get the Smallest Common Multiple of 2 numbers, but the challenge asks for Smallest Common Multiple of ALL numbers between 2 numbers.

and i don’t think that you can predict the number of Multiples beforehand . (the units variable)

well, i solved the challenge without any array so i may give a little hint

For [1,5] : (1 2 3 4 5)
potential SCM : 5 10 15 20 25 30 35 40 45 … 60 …
but Real SCM : is 60

i hope that will help you ^^

3

Thanks man, thats ok i’m confused with my code as well. I just need some help. You said you didn’t use an array, but how can I create something of the sort that will hold the potential SCM without knowing how big it will be? Maybe a for loop that will multiply 5 * i? but how do I make it stop when it has come to the right SCM?

My next question is how do I check the potential SCM against all the numbers in the range to determine if it is the real SCM because I don’t know how big the range will be.

Thanks for your help.

4

You’re welcome :slight_smile:
well , first 5 is just the max of the given numbers in that example,

you can solve the problem using an infinite loop (while) ,
in which you create the next potential SCM, and check if it is a multiplier of all numbers between the two given numbers (using a for loop ).

as i said you can’t predict how many multipliers you should check before you find the SCM,

good luck !

5

This problem really has me stumped. I would appreciate a few more hints. I struggle with while loops, and I still can’t figure out how I would use it to collect a potential infinite number of SCM’s as well as have a for loop nested in it. Let’s take the actual SCM for example. In this case it is 60. I don’t understand how to check to see if 60 leaves no remainder for all of the potential numbers within a range. My thinking is to do something like this

if (60%2 === 0 && 60%3 === 0 && 60%4 === 0 && 60%5 === 0) {
   return 60;
}

but I can’t do this because there could potentially be more numbers within the range. I want to get the potential SCM, divide it by all potential numbers in a range, and if it is not divisible by all potential numbers in a range, I want to go to the next potential SCM. If it is divisible by all numbers in a range I want to return the number and end the loop.

6

to see if a number is a multiplier of all numbers within a certain range, you can use a helper function like this :

function isCommonMultiplier(number,rangeStart,rangeEnd){
    // number is a potential SCM
    for ( var i = rangeStart; i <= rangeEnd; i++){ 
        if ( number % i !== 0){ // if number is not a multiplier of i
            return false;
        }
    }
    return true; // we are here because number is a multiplier of all numbers in the given range
}
1 Like
7

Thanks man, I got that while loop figured out I appreciate it.

8

Some mathematical trickery that could simplify the process.

The Least Common Multiple(LCM) of 2 numbers is the product of the 2 numbers divided by their Greatest Common Denominator(GCD). GCD of 2 numbers can be derived through Euclidean Algorithm.

I solved the challenge with 2 different approaches.

1 is I have a way to find the LCM of 2 numbers fairly efficiently, so all I have to do is to find the LCM between the first 2 numbers, then find the LCM between that number and the next number, and work my way down the line.

Example:
I want to find the smallest common multiple of range [ 2, 3, 4, 5].

First I find the LCM of 2 and 3, and it’s 6,

then I find the LCM of 6 and 4, which is 12,

last I find the LCM of 12 and 5, which is 60.

The other approach is slight more complicated. It involves prime factorization of all the numbers in range. It’s more verbose but more memory effcient

2 Likes