Stuck on Smallest Common Multiple challenge

Stuck on Smallest Common Multiple challenge
0.0 0

#1

Hey guys,

I’ve been stuck on this problem for a few days now and i’ve totally redone my indent preformatted text by 4 spacescode for it once. My algorithm can find the lcm of 2 numbers and check if the numbers in between the input numbers can divide evenly into the lcm, but I don’t know how to find the next lowest lcm if the actual lcm isn’t divisible by the middle numbers.

Any ideas on how to do this with the code that I have?

Thanks

// Main problem: How do I find the next common multiple if the LCM isn't divisible by all nums inbetween???

function gcd(a, b){ // a and b are integers
  if(b === 0 || a === b)
    return a;
  else if(a > b)
    return gcd(a-b,b);
  else if(b > a)
    return gcd(a,b-a);
}
//Test
//console.log(gcd(54,24)); //returns 6

function lcm(a,b){ // a and b are integers
  var lcm = (a*b)/gcd(a,b);
  /*
  for(var i = 0; i < arr.length; i++){
    lcm = (lcm * arr[i]) / gcd(lcm, arr[i]);
  }*/
  return lcm;
}
// Test... does work when nums are flipped ie. [1,5] is same as [5,1]
//console.log(lcm(8,6)); //returns 24

function numsBetween(arr){ // Returns an array of the the nums between and including the 2 elements in the input     array
  var num1 = arr[0],
      num2 = arr[1],
      btwn = [];

  for(var i=num1; i<=num2; i++)
    btwn.push(i);

  return btwn;
}
// Test
//console.log(numsBetween([1,5])); //will return [1,2,3,4,5]

function areBtwnsMultiples(lcm, btwns){ //Checks to see if nums in between are multiples of the lcm. 'btwns' is an     array of nums
  var mults = true;
  btwns.forEach(function(num){  //For each num in btwns, if the proposed lcm isn't evenly divisible, then not all nums     are multiples of the proposed lcm 
    if(lcm % num !== 0)
      mults = false;
  });
  return mults; //Return true if all nums divide evenly into the proposed lcm
}
// Test
//console.log(areBtwnsMultiples(60,[1,2,3,4,5])); //will return 'true'

function smallestCommons(arr) {
  //1) get gcd using formula (done inside lcm function)
  //2) get lcm using gcd and lcm formula
  var lcm = lcm(arr[0], arr[1]);
  //3) make sure all in between numbers also divide into the lcm
  if(!areBtwnsMultiples(lcm, numsBetween(arr)))
    // Find the next lcm... but how???
  //4) return the lcm
  return lcm;
}

//var ans = smallestCommons([1, 5]); //should return 60. 
//var ans = smallestCommons([5, 1]); //should return 60. 
//var ans = smallestCommons([1, 13]); //should return 360360. 
//var ans = smallestCommons([23, 18]); //should return 6056820.

console.log(ans);

#2

If you want to stick to your current logic, then in addition to just checking if nums in between are multiples of the initial lcm candidate, you need to remember which ones weren’t (perhaps by returning them from areBtwnsMultiples function, and returning -1 or some other “flag” value if the lcm candidate is the actual lcm) - then multiply the lcm candidate by smallest of them, and check it again.

But probably easiest way to deal with it instead is to take advantage of the fact that lcm(a,b,c) = lcm(lcm(a,b),c) and go through the numsBetween array with this logic. It is a good opportunity to learn about array.reduce() :slight_smile:


#3

Thanks for the reply! And yes, I ended up utilizing array.reduce() :slight_smile:


#4

when I look at the lowest common multiple of 1 and 5 (ie) the example, I get 5.

How does 1,5 = 60?

I used this page to check my answer.

I understand the “sequential” part of the problem, where 1-5 is a range… But still, I don’t get 60, even when i use the tool in the link above??


#6

You basically have to do a lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, lcm(4,5)))).
You don’t just get the lcm of 1 and 5. That does equal 1, however, you need to do the entire range.


#7

Yeah, I’m sorry I still don’t get hoe it equals 60?

do I need to factorialize the number or something? 1x2x3x4x5?

how does it add up to 60? I just want to understand that before starting the challenge…


#8

Why factorialize? I gave you the formula: lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, lcm(4,5)))). You make use of the associativity: lcm(a,b,c) = lcm(a, lcm(b,c))

You take the lcm of each of the numbers:

lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, lcm(4, 5))))
lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, 20)))
lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, 60))
lcm(1, 2, 3, 4 ,5) = lcm(1, 60))
lcm(1, 2, 3,4, 5) = 60;

for instance, if you would have to do the problem from 18 - 20, you would do:
lcm(18, 19, 20) = lcm(18, lcm(19,20))
lcm(18, 19, 20) = lcm(18, 380)
lcm(18, 19, 20) = 3420


#9

I’m really sorry, but I don’t understand :frowning:

is there anywhere I read up about this? because the lcm calculators online dont ever reach 60 in a range of 1 to 5…

I feel like an idiot and don’t know what this means, are you doing multiplication to get to 60?:

lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, lcm(4, 5))))
lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, lcm(3, 20)))
lcm(1, 2, 3, 4, 5) = lcm(1, lcm(2, 60))
lcm(1, 2, 3, 4 ,5) = lcm(1, 60))
lcm(1, 2, 3,4, 5) = 60;

Sorry again for being a n00b


#10

No multiplication. It’s the normal return value of LCM. It seems you are confused about that o.O

For 2 integers a and b, denoted LCM(a,b), it is the smallest integer that is evenly divisible by both a and b.

Say we are trying to figure out what lcm(2,3) equals to. The result is 6, because:

multiples of 2: 2, 4, 6, 8, 10, 12,…
multiples of 3: 3, 6, 9, 12, 15,…

as you can see, number 6 is the smallest possible integer, that is evenly divisible by both 2 and 3, thus making it lcm.

Same goes for any other two numbers. Now, if you have more than one number, which we have, in the case of the challenge, the lcm is the smallest intiger, that is evenly divisible by all the numbers. So, if we are looking for lcm(1, 2, 3, 4,5), we have to find the smallest intiger, that is divisible by all of them.

multiples of 1: everything.
multiples of 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, …, 50, 52, 54, 56, 58, 60, 62, 64,…
multiples of 3: 3, 6, 9, 12, 15, 18, …, 51, 54, 57, 60, 63,…
multiples of 4: 4, 8, 12, 16, 20, …, 52, 56, 60, 64, 68,…
multiples of 5: 5, 10, 15, 20, 25, 30,… , 50, 55, 60, 65, …

If we follow the previous rule, we see that there are no numbers below 60, that would be evenly divisible with all our numbers. 60 is the smallest integer however, that is, thus making it the lcm of our number set.

The lcm calculators do reach 60 in range of 1 to 5, as we can see in the upper example: http://www.calculatorsoup.com/calculators/math/lcm.php

You don’t multiply the numbers together ( however, in some cases, LCM can be the multiplication of the two numbers, as seen in lcm(2, 3) = 6 or lcm (1, 5) = 5.

Is it any clearer now? I apologize, cause my “explaining” skills really do need some polishing. Also, in my opinion, you never need to apologize if you don’t know something and you’re eager to learn about it :slight_smile: It’s normal that you have questions, so don’t stress out too much :slight_smile: Also, if you still can’t understand something about it, just tell me, and i’ll keep explaining it as best I can :slight_smile:

also, to learn more about lcm: https://en.wikipedia.org/wiki/Least_common_multiple


#11

THANK YOU so much, that was an awesome explanation. I really really appreciate the effort you went to explaining it.

I understand it better now but still am a bit rusty on my math so figuring out a proper algorithm will be tricky :open_mouth:

I will write it out like you have for each number just to get my head around it, and then go from there :slight_smile:

Thanks again!!!


#12

This information will help => thanks for the Wiki Link

A simple algorithm
This method works as easily for finding the LCM of several integers.

Let there be a finite sequence of positive integers X = (x1, x2, …, xn), n > 1. The algorithm proceeds in steps as follows: on each step m it examines and updates the sequence X(m) = (x1(m), x2(m), …, xn(m)), X(1) = X, where X(m) is the mth iteration of X, i.e. X at step m of the algorithm, etc. The purpose of the examination is to pick the least (perhaps, one of many) element of the sequence X(m). Assuming xk0(m) is the selected element, the sequence X(m+1) is defined as

xk(m+1) = xk(m), k ≠ k0
xk0(m+1) = xk0(m) + xk0(1).
In other words, the least element is increased by the corresponding x whereas the rest of the elements pass from X(m) to X(m+1) unchanged.

The algorithm stops when all elements in sequence X(m) are equal. Their common value L is exactly LCM(X).

A method using a table
This method works for any number of factors. One begins by listing all of the numbers vertically in a table (in this example 4, 7, 12, 21, and 42):

4
7
12
21
42
The process begins by dividing all of the factors by 2. If any of them divides evenly, write 2 at the top of the table and the result of division by 2 of each factor in the space to the right of each factor and below the 2. If a number does not divide evenly, just rewrite the number again. If 2 does not divide evenly into any of the numbers, try 3.

x 2
4 2
7 7
12 6
21 21
42 21
Now, check if 2 divides again:

x 2 2
4 2 1
7 7 7
12 6 3
21 21 21
42 21 21
Once 2 no longer divides, divide by 3. If 3 no longer divides, try 5 and 7. Keep going until all of the numbers have been reduced to 1.

x 2 2 3 7
4 2 1 1 1
7 7 7 7 1
12 6 3 1 1
21 21 21 7 1
42 21 21 7 1
Now, multiply the numbers on the top and you have the LCM. In this case, it is 2 × 2 × 3 × 7 = 84. You will get to the LCM the quickest if you use prime numbers and start from the lowest prime, 2.


#13

I had to watch a couple of Khan Academy videos to figure this one out :blush:

Learning about prime factorization helped me with my solution :slight_smile:


#14

No problem :slight_smile: I have some advice tho, considering you are entering into the world of computer science, you should really refresh the math part. No need to go super specific and deep, just refresh on the common things. Programming and computer science in general is all about math :slight_smile:


#16

Here’s my working for the first problem so far. I built a table to visualize how 1-5 gets to 60

±–±--±–±--±–+
| x | 2 | 2 | 3 | 5 | ===========> ANSWER = 223*5 = 60
±–±--±–±--±–+
| 1 | 1 | 1 | 1 | 1 |
±–±--±–±--±–+
| 2 | 1 | 1 | 1 | 1 |
±–±--±–±--±–+
| 3 | 3 | 3 | 1 | 1 |
±–±--±–±--±–+
| 4 | 2 | 1 | 1 | 1 |
±–±--±–±--±–+
| 5 | 5 | 5 | 5 | 5 |
±–±--±–±--±–+

So far I have sorted the array =>
arr = arr.sort((a,b) => { return a - b; });

Then I have returned all the nums from 1 to arr max
var arrNums = Array.from({length: arr[1]}).map( (el,i) => i + 1 );
//arrNums = [1,2,3,4,5]

And now I need some sort of counter to count up if the num isn’t divisible by 2,3,4,5 etc…


#17

So far I’ve nearly cracked it – I get all but the last because of an infinite loop problem…
I need some sort of break, or maybe a do while loop?
Any suggestions?

function smallestCommons(arr) {

  var divisible;
  var count = 1;
  arr = arr.sort((a,b) => { return a - b; });
  
  // Generate a sequence of numbers
  var arrNums =  Array.from({length: arr[1]}).map( (el,i) => i + 1 );
  
  while (arrNums) { 
  // every() tests whether all elements in the array pass the test
     divisible = arrNums.every((number) => {  
        return count % number === 0;         
     });

    // if divisible return the result, else increment count    
        divisible ? count : count++;  
  }
  
}

smallestCommons([1,5]);
smallestCommons([1, 13]);

#18

I tried your code and it doesn’t work, I get infinite loop every time.

I can’t see where are the conditions to leave the while loop - you are checking if arrNums is true, but you have no place where you are changing arrNums neither you have return anywhere to break out of the loop.


#19

Yeah… I return count at the end, otherwise count++

It worked for me the first time for every challenge and I got all ticks, but now it has stopped me because fo the infinite loop.0_o

I’m not too sure how to break this…


#20

I realised a massive flaw in my code when using the length property below
var arrNums = Array.from({length: arr[1]}).map( (el,i) => i + 1 );

This is calculating the length from 1 to N ( not supplying a range like required )

I made aa much simpler function to get the range properly each time…

function range(a, b) {
  var arr = [];

  while (a <= b) {
    arr.push(a++);
  }

  return arr;
}

#21

One formula you can use to find the lcm is to first find the gcd. Once you do that the lcm for say lcm(4, 20) would be 4 * 20 / gcd(4,20). Google euclid’s algorithm.


#22

Thanks for the tip!! I revamped my code to reflect that. Oh man, I really need to brush up my math skills :open_mouth:
But I managed to crack it in the end, thanks to Wikipedia and the GCD and LCM formulas. Here’s what I got:

function smallestCommons(arr) {
   /** 
     Notes on algorithm
     GCD = Greatest Common Divisor
   * the GCD of two or more integers is the largest number  
   * divisible without a remainder => eg. the gcd(4,8) === 4.
     LCM = Lowest Common Multiple
   * the LCM multiplies arr[0] * arr[1] and divides it by the result of the GCD.
   * eg. 4 * 8 / 4 = 8;
     Map function
   * We iterate through the given array and input the LCM algorithm.
   * Then return the result, which will multiple the LCM for each number.
   **/
  
  // Sort the array from smallest to biggest
  arr = arr.sort((a,b) => { return a - b; });  
  // Create a range function
  const range = (min, max) => {
      var temp = [];
      while (min <= max) {
        temp.push(min++);
      }
      return temp;
  };
 
    // GCD function
    const gcd = (a, b) => {
        return b === 0 ? a : gcd (b, a % b);
    };
    // LCM function
    const lcm = (a, b) => {
        return (a * b) / gcd(a, b);   
    };
    // Find the multiples starting with lowest number
    var multiple = arr[0];
    range(arr[0], arr[1]).map((num, i) => {
        multiple = lcm(multiple, num);
        console.log(num + ": " + multiple);
    });

    return multiple;
}

smallestCommons([4, 8]); // => 360360