How to find the smallest common multiple or LCM?

JavaScript
#1

Hello campers,

I need a help in order to understand the algorithm of finding the LCM between two numbers or even more. I need to understand what is the way to find that common multiple in order to pass this challenge: https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple

I’ve tried to google but without result :frowning:

Please note, I DO NOT NEED CODE SOLUTION. I need some instructions like:

  1. do this
  2. find that
  3. then compare
  4. etc…

I will appreciate any help! Thanks!

#2

I really struggled with this, too!

I came up with an extremely inelegant solution by looking up how to figure out the LCM for two numbers using the factor tree method on some maths for kids website, and then writing a convoluted algorithm that repeated that process for all the numbers in a range.

It was ugly, but it worked :stuck_out_tongue:

#3

Lets’ tackle the problem using the example of the [1,3] common multiple, aka, a number that has a rest of 0 when dividing by both 1 and 3.

For this first part create a while loop that will stop when our number, in this case 3, is found and keep a counter so we know which number we’re at.

After you have that you’re not done yet because of the second part of the challenge, all the number between 1 and 3 must also be divisible so not only 1 and 3 but also 3 must be divisible and 2 % 3 is not 0 so our previous found 3 won’t work.

To fix that before you break the infinite loop you’re going to do a loop that starts at 2 and ends before 3 (in this case it will loop only once) and check if the current infinite loop number is divisible by your loop number, 3 % 2 will fail so we don’t break the infinite loop until we find or value, which is the expected 6.

This way you should have a working loop inside a loop that breaks when the conditions are met.

#4

that’s the kind of algorithm that will be prematuraly stopped by the infinite loop protection, as for the [18,23] you need 6 million and a half iterations for your infinite loop approach. too much.

#5

Yes, you’re right that it will iterate quite a bit it won’t timeout though, 6 million iterations is nothing especially given the complexity of the operations and can be cut earlier with proper checks.

There are faster and better approaches using LCM formulas which weren’t my worry when explaining how you can think of a problem and solve it as requested by @timagixe.

This is the solution based on my reply and it passes the tests without performance problems (no peeking until you solve it @timagixe :smile: )

function smallestCommons(arr) {
  let stopLoop = false
  let multiple = 0
  const orderedArr = arr.sort((a, b) => a - b)

  while(stopLoop === false) {
    multiple++
    
    for (let i = orderedArr[0]; i <= orderedArr[1]; i++) {
      if (multiple % i === 0) {
        stopLoop = true
      } else {
        stopLoop = false
        break
      }
    }
  }
  
  return multiple
}

Edit: Removal of redundant loop

#6

There’s a famously elegant algorithm to calculate GCD.

lcm(a,b) is simply (a*b)/gcd(a,b)

2 Likes
#7

If you think you need an infinite loop to do a calculation… you really don’t… That’s never a good idea.

#8

The loop is not, in fact, infinite, my bad with the wording, edited

1 Like
#9

For challenges like this, it is perfectly legitimate to look up mathematical or logical formulas. Learning to translate a logical model into code is an important skill. Wikipedia is a pretty good resource for things like this because those articles tell you what you need to do but don’t give you code for solving it programmatically.

1 Like
#10

Hello, thank you all for joining the discussion :slight_smile:

This one looks fine but it will not work if I have more than two numbers. For example:
lcm(1,2,3,4,5) it should be 60, however if I follow the formula you provided I will receive 120:
lcm(1,2,3,4,5) = 1*2*3*4*5 / gcd(1,2,3,4,5) = 120 because of denominator is equal 1.

I also think that such tasks are great for practice. That’s why I followed this way.

I’m working further on solving this algorithm.

#11

Ah, but the LCM has the great property that
lcm(a_0, a_1, ..., a_n-1, a_n) = lcm(lcm(a_0, a_1, ..., a_n-1), a_n)

In mathematics, you’re golden if you can link the big case back down to the smallest case!

#12

Thank you for the idea!

I’ve implemented GCD function for [x,y] numbers and LCM function for them.

And then when I have a range of numbers i.e. 5,6,7,8 (where x = 5, and y = 8) I used your formula and it worked!

But it actually took me pretty long time to solve it :slight_smile:

1 Like
#13