Hitting a roadblock on Smallest Common Multiple, my code is a mess

Tell us what’s happening:
Below is the only code that I can confidently write. Everything else is a seething mass of variables that seem to have little to no connection to the code, placeholders that are likewise, etc. etc.
I’ve read through Euclid’s Algorithm and I’m trying my darnest to convert that to JS, but I’m really not managing, so below I have a mix of code and comments and what I’d like is someone to point to what my logic is doing wrong. I realize there are serious errors in logic, but I’m not sure how to conceptualize or phrase HOW I’m going wrong. If some could help me with this, then I would appreciate it.
You can be blunt. It’s fine. I actually prefer bluntness. But just note that I am aware of my deficiencies as a coder, so you don’t need to state this particular fact.

Thank you!

Your code so far


function smallestCommons(arr) {
//sort array 
arr = arr.sort((a,b)=> a-b);
//set up empty array and variables
  let array = [];
  let a, b, c, d;
//use for loop to push all elements in arr as well as all elements in between elements in arr into array
  for(let i = arr[0]; i <= arr[arr.length-1]; i++){
    array.push(i);
    console.log(array)
  } 
//Set up second loop to iterate through array and provide values for variables that will complete Euclid's algorithm
//Euclid's algorithm key chart being the following: a= dividend; b=divisor; c=quotient; d=remainder
 for(let j = array[array.length[0]]; j <= array[array.length-1]; j++){
//Variable a has  element in array of j iteration and b assigned to element one greater than value of a variable
a = array[j];
b=array[j+1];
//c quotient of b/a
c = b/a;
//d is remainder of b/a
d = b%a;
//while a and b are truthy values, perform Euclid's Algorithm
while(a&&b){
a = b*c + d;
//if the remainder is 0 then return a, else break code and break 
if(d === 0){
return a
} else if {
break;
}
}
}
}


smallestCommons([1,5]);

https://www.mathsisfun.com/least-common-multiple.html

This site helped me a lot on this exercise.

Finding the Least Common Multiple

I made a function to get this in a step by step manner just like I would do it on paper for just two numbers.

Then I made another function that would take an array and use the reduce method with my first function as a callback.

After that I added the functionality to make a range of numbers array from the two number array you start with.

I worked on this after reading your post. I was looking at the examples solutions from the hints and they all seemed complicated to me.

I tried a few things but came up with my own solution when I just tried to understand the problem on a fundamental level, like how would I do it with pencil and paper.

I’m having difficulty discerning what is the exact difference between the two algorithms below. The first one is a suitable answer and the other is not and only passes the first test. Below I have my concerns and questions:
First one:

function smallestCommons(arr){
arr = arr.sort((a,b)=>a-b);
let[x,y] = arr;
while(x<arr[1]){
if(y%x===0){
x++
} else {
y+=arr[1];
x=arr[0];
}
return y;
}

Second One:

function smallestCommons(arr) {
  arr = arr.sort((a,b)=> a-b);
  let x = arr[0];
  let y = arr[1];
  while(x<y){
    if(y%x===0){
      x++
    } else {
      y = y+y;
      x = x+x;
    }
  } console.log(y)
  return y;
}

I think the problem with the second one is that I don’t have the original value and that that is necessary for the iteration. I’m not exactly sure why this is, but I find that it’s the only difference between them. Perhaps I’m misinterpreting what += means. I’d really like to find out where I’m not understanding the correct solution.

Thank you.

The second one is almost infinite loop, but it doesn’t freeze because it keeps doubling y and x until both x and y equal Infinity and while (Infinity < Infinity) {...} evaluates to false, breaking the while loop and returning Infinity.

You are right that you need the original value so you can increment x and y by their original value.

The first solution while loop breaks too early because you increment x and y by the original values, which is what you want to do, but (x < arr[1]) will be false and break the loop as soon as x is greater than arr[1].

Figuring out what’s going on is a lot easier if you are using a debugger that you can step through each line of code.

You can do this in a local dev environment but I like to use Chrome snippets feature of the chrome dev tools. Do you know how to use that or are you using a debugger locally? Or just working the problem on the freecodecamp itself?

https://developers.google.com/web/tools/chrome-devtools/snippets

I may edit this post and I will try to write the pseudo code of my approach to first get the LCM of two numbers.

So we are working with two numbers to start 4 and 10. We need to find the smallest multiple of both numbers that our original numbers will divide into evenly. This will be the first number that matches if we write out all the multiples of each number as shown in the picture.

So lets create a while loop to check for that condition, and I’ll call the variables that we will increment max and min and set those to the original number inputs.

// This example assumes a will always be largest otherwise
// an infinite loop will occur
function findLCM(a,b) {
  let max = a;
  let min = b;

  while(max !== min) {...}
}

You could also write, which I originally did, while(max % min !== 0) but I think I prefer the former, in this case the results will be the same.

So taking the former condition, when max is not the same number as min we need to check if the next multiple of min is equal to max so in the while loop we add the original min number stored in the b parameter to min.

min = min + b

The while loop condition now checks if our updated min is now equal to max and it is not so then it performs the same function, adding b to min.

By the second iteration our min is larger than our max and we don’t ever want that so before adding b to our min we should check with an if statement if min > max and if that is true we will increment max to it’s next multiple.

The way I did this was to not run min = min + b unless max was greater than min.

if (max > min) {
  min = min + b;
} else {...}

So once min becomes greater than max we increment max and we can also increment min with it since the next multiple of max will always be larger than the current min.

This will save us a step in the iteration of our while loop but you could just only increase the max at this point and it will still work just with a few more loops happening. I feel like there is a way to make the whole thing more efficient as well but not too concerned for this exercise at least.

I’m starting my sentences with so too much…so after four iterations our min reaches 20 which is the smallest common multiple of 4 and 10 and min and max will be equal to 20 and you could return either variable.

This is the first part of this challenge. The second part is using this function to get the smallest common multiple of a range of numbers. You could do all this in one function but I preferred to solve it in two functions.

This function we wrote will be perfect to use with the Array.prototype.reduce method because if you have an array [5,4,3,2,1] reduce will take the function we made as a callback and…

It will first do 5 and 4 and get the LCM and then that number will be a and b will be the next number in line 3 and so on. Processing the array from largest to smallest will be most efficient according to Hint # 3 from the Get a Hint page because they are more likely to be the smallest common multiple than the lower numbers.

This was my personal approach and thought process for this exercise, sorry it was so long winded I need to work on my conciseness. Let me know if this helps or further confuses you.

This is really great. I don’t understand everything said on the first read, but the language is clear and I’m so excited to go back over this challenge and apply the logic you spoke about to what I was trying to apply in the challenge in the first paragraph of code.

Thank you.

I would first try to see if you can assemble the function that returns the LCM of just two numbers.

I’m tempted to write some pseudo code but I don’t want to rob you of the learning experience.

And you are half way through the intermediate algorithm section if you are going in order and that is a great accomplishment.

In my opinion this algorithm section and the projects for it are the hardest part of the whole FreeCodeCamp curriculum in terms of cognitive load so don’t despair, don’t burn out, and don’t feel guilty for taking breaks or sleeping on it.

Many breakthroughs happened for me after failing to solve these problems and taking a break or the next day after I slept well.

Feel free to ask more questions if needed.

Edit: Just want to mention that my solution would probably be considered a brute force style solution and therefore basic and using Euclid’s Algorithm would be a more efficient approach and a more advanced solution.

A question on one of your earlier comments:

The first solution while loop breaks too early because you increment x and y by the original
values, which is what you want to do, but (x < arr[1]) will be false and break the loop as soon as x is greater than arr[1] .

Referring to this in my code: while(x < arr[1])

But I think I address this issue in the else statement I make wherein if y and x are not divisible (and therefore not multiples), then y is incremented by the value of arr[1] while x remains assigned to the value of arr[0] and, therefore, remains lesser than y

if(y%x===0){
x++
} else{
y+=arr[1];
x=arr[0]

}

}

My apologize you are correct. I read your code wrong. I thought it had incremented x there. I hope that didn’t cause you too much extra headache.

And it probably did since it passes the tests. Very sorry I missed that.

Edit: Digging in to the problem more I see your solution is much more efficient than my solution.

Using the Euclidean Algorithm of course is more efficient, but it’s quite amazing how much more efficient it actually is.

One of the intermediate solution examples explains to calculate the smallestCommons(1,25) takes about 40 loops using the algorithm.

The basic example solution takes over 4 million, your solution takes over 3 billion, and mine…never finishes lol.

1 Like

Euclid’s algorithm is not just a lot more efficient, it’s just about the most elegant algorithm ever when you use the recursive version:

const gcd = (a,b) => b ? gcd(b, a % b) : a

// and just for completeness...
const lcm = (a,b) => a * b / gcd(a, b)

It was getting the “gcd of a range” part that actually had me stuck for several hours.