[Solved] Smallest Common Multiple Algorithm Challenge -- getting stuck in a loop

[Solved] Smallest Common Multiple Algorithm Challenge -- getting stuck in a loop
0.0 0

#1

Hi all,

I’ve been working on the Smallest Common Multiple challenge for the past few days, and I’ve finally made some progress. I was originally trying to implement a complex solution using an LCM algorithm and a recursive function. I put that on hold and decided I should try and get a solution working with a simple brute force program first.

I’m hitting a wall with my simple brute force solution.

Here’s my code: https://pastebin.com/547zHRK9

What I’m trying to do

  • I’m creating an array with the entire range of numbers between the provided two digits.
  • I’m then sorting the array from largest to smallest.
  • I then have a while loop checking the smallest multiple of the first two numbers against the other numbers in the array. I’m getting this multiple from a custom function. If the multiple does not divide evenly with one of the range numbers, the custom function is called again (but this time it will exclude the previous smallest multiple), and the next smallest multiple of the two first numbers is checked against the range of numbers (this is supposed to be repeated until a multiple is found that divides evenly with all the range numbers).

This isn’t happening as planned.
The program works correctly with some number ranges (such as [1, 3], [1, 4], and [1, 6]), but not with others ([1,5] gets stuck in an infinite loop).

Can anyone give me a nudge in the right direction? Also, is there a better solution that using while (true) loops, like I have in the current code?

Thanks!


Update: The assistance provided by @honmanyau helped solve the infinite loop issue. My code still doesn’t pass all checks, but the issue I was asking about above has been solved.

Here’s my code with the fixed secondary function call (finding the smallest common multiple of two numbers, and excluding an included third argument): https://pastebin.com/JLgZXPEF


#2

To be honest, I personally feel very uncomfortable with the while(true) {...} loops—particular because the condition is always true (well, true is always true!) and the only way that you are breaking out of the loop is with break or return.

Anyhow, I think the reason that it’s not working is because the logic in smallMultiple() is not quite right. Currently your algorithm works like this (suppose the first multiple found is not divisible by range[2]):

  1. Pass the first two numbers in range, range[0] and range[1], into smallMultiple()
  2. Find the “mini” smallest common multiple (SCM) between range[0] and range[1]
  3. Once the mSCM is found between range[0] and range[1], return it
  4. Check the mSCM is divisible by range[2]
  5. If it is not divisible by range[2], assign the current mSCM to nocheck
  6. Pass the first two numbers in range, range[0] and range[1], into smallMultiple()
  7. Find the smallest common multiple (SCM) between range[0] and range[1]
  8. Try to find the mSCM between range[0] and range[1]—because nocheck/exclude is now the same as the SCM, iterate will keep increasing until the next smallest multiple is found, which is mSCM * 2
  9. Suppose the smallest multiple is still not divisible by range[2]
  10. Find the smallest common multiple (SCM) between range[0] and range[1]
  11. Try to find the mSCM between range[0] and range[1]—because nocheck/exclude is now the same as the mSCM * 2, this time mSCM will be returned

You probably can see where the infinite loop is now. :slight_smile:

The second problem is that, if I’m not mistaken, your algorithm won’t solve larger ranges. Let’s take [1, 8] as an input—the first mSCM from your algorithm is 56, even if iterate keeps increasing as you intend it to, it will skip 420, which is the solution—the reason is, if I’m not mistaken, because your algorithm is only ever using the first three numbers range.

That’s all I have for now at this point. Good luck!


#3

Awesome response – thanks for taking the time!

This gives me a lot to review.


#4

Ok, I seem to have fixed the infinite loop problem (I think).

In my new smallMultiple() function, I’ve removed the exclude variable. Now, I’m only using the iterator variable, which I use to update based on the provided third argument. I also removed the while (true) loop. Here’s my new function:

function smallMultiple(a, b, iterate) {
    if (iterate === 0) {
        iterate = 1;
    } else {
        iterate = (iterate / a) + 1;
    }
    
    while (a * iterate % b !== 0) {
        console.log(iterate);
        iterate++;
    }
    
    return a * iterate;
}

My code now passes the checks for all the test parameters, except the last one ([23, 18]):


I’ve tried debugging with a console.log() inside the smallMultiple() function (printing iterator), and it looks like the program crashes at a certain point when the numbers become too large. I think my main issue now is using the brute force method.

Here’s my current code, anyway: https://pastebin.com/JLgZXPEF


Again, thank you @honmanyau for the help!


#5

you may well have looked at all this before but just in case…

it helps to consider that this is a relatively common mathematical method – which is to say that some ancient Greek figured it out a long time ago, and thus people in the Common Era have figured out how to write the Greek’s method into computer code. So, these references may be useful: https://en.wikipedia.org/wiki/Least_common_multiplehttps://en.wikipedia.org/wiki/Greatest_common_divisor

if it helps for reference, since you’ve gotten far enough along that it’s not really “cheating” (fwiw), take a look at the “official” fCC reference for this challenge: https://forum.freecodecamp.com/t/freecodecamp-algorithm-challenge-guide-smallest-common-multiple/16075


#6

First and foremost, I want to tell you that even if the code did compile, the answer would be wrong because I made that same mistake when I was coding that challenge. You are checking the wrong range. The prompt asked for the smallest common multiple of all the number between the 2 numbers, so instead of the range being 1 to 23, it should be 18 to 23.

I find it odd that you only check the multiple of the first 2 numbers in your range.

I think the most common logic for this problem is to find the least common multiple of 2 numbers, then find the least common multiple of that number and the next number, so on and so forth until you run out of numbers.

like say you have a range of 4,5,6,7,8

  1. You would find the LCM of 4 and 5, which is 20
  2. Now find the LCM of 20 and 6, which is 60
  3. Find LCM of 60 and 7, which is 420
  4. Finally find the LCM of 420 and 8, which is 840

What you seem to be doing is

  1. Find the LCM of 8 and 7, which is 56
  2. See if it’s divisible by 5, if not, multiply by the increment of 1
    …so on so forth

so just to get to 840, you ran 105 iterations, almost every prime number you run into increases the iteration by an order of magnitude. 13 was coincidentally the boundary, once you run into 17, the program crashes.


#7

Thank you!

I see my main fault now (and feel completely incompetent for not picking up on it sooner :joy:).