Smallest Common Multiple - call stack exceeded

Smallest Common Multiple - call stack exceeded
0

#1

I get an error:
“Maximum call stack size exceeded”
There is a recursive function.
It has a base and a termination point.
But it seems they don’t work.
Is there a chance for this code?
Please help.
After the comment of ArielLeslie(totally not a bot)
I modified the code:
And now the code checks if all the elements
have the same smallest perfect divisor, and it comes to a point,
where all elements return true.
The problem is that it doesn’t stop the iteration.
There is an iterate boolean , which turns to false at the end, but then at the beginning it gets assigned to true again.
Is there a way to fix that?
Or is there another way to make this work?

The code below is set to iterate 8 times. That’s the point where it should stop. If set to 9, it just goes on.

When the problem will be fixed the hard coded for loop will be changed to while (iteration) , if that’s OK.


  function smallestCommons(arr) {

      arr.sort();
      // get the numbers between the two elements
      let numbers = [];
      let secondElement = arr[1];
      for (var i = 0; i < secondElement; i++) {
        numbers.push(arr[1]--);
      }

      function findCommon(arr) {

        let multiplier = arr[0]++;
        let multiplies = [];
        let booleans = [];

        // multiply all elements with multiplier
        // and store the values in multiplies
        for (var i = 0; i < arr.length; i++) {
          multiplies.push(arr[i] * multiplier);
           multiplier++;
        }
        // check which elements of the multiplies
        // array have a perfect division
        // with the first element
        // of the multiplies array
        // and push the boolean results in a array,
        for (var i = 0; i < multiplies.length; i++) {
          booleans.push(multiplies[i] % arr[0] === 0);
        }

        // count the elements that are true
        let trueValues = 0;
        for (var i = 0; i < booleans.length; i++) {
          if (booleans[i] === true) {
            trueValues++
          }
        }

        // if all elements are true
        // return the first element.
        if (trueValues === arr.length) {
          return multiplies[0];
        }

        // repeate the process
        // until all elements are true
        // This seems like a double check.
        if (trueValues < arr.length) {
          findCommon(arr);
        }

        console.log(multiplies);
        console.log(booleans);
        console.log(trueValues);


      }

      let result = findCommon(numbers);

      return result;
    }

    smallestCommons([1, 5]);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.100 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple


#2

Your findCommon function only ever returns if trueValues === arr.length and there doesn’t appear to be a base case. A recursive function should always return. On top of that, within findCommon you call findCommon again with arr, which is the same parameter you passed it in the first place. Therefore it will run exactly the same way every time. Either your trueValues === arr.length condition will be true and the function will return the first time its called, or it will keep calling itself until you crash.


#3

Thanks for your help. :slight_smile:
The code checks if all the elements
have the same smallest perfect divisor, and it comes to a point,
where all elements return true.
The problem is that it doesn’t stop the iteration.
There is an iterate boolean, which turns to false at the end, but then at the beginning it gets assigned to true again.
Is there a way to fix that?
Or is there another way to make this work?

The code below is set to iterate 8 times. That’s the point where it should stop. If set to 9, it just goes on.

When the problem will be fixed the hard coded for loop will be changed to while (iteration) , if that’s OK.

      function smallestCommons(arr) {

      let newArr = arr.sort();
      // get the numbers between the two elements
      let numbers = [];
      let secondElement = arr[1];
      for (let i = 0; i < secondElement; i++) {
        numbers.push(newArr[1]--);
      }
      console.log(numbers);


      // find the smallest common perfect divisor
      function findCommon(array) {

        let newArray = [...array]
        let multiplier = newArray[0];
        let product = 0;
        let iterate = true;
        // multiply the first element with multiplier
        // and store the product
        for (let i = 0; i < 8; i++) {
          if (iterate) {
            product = newArray[0] * multiplier++;
            console.log('multiplier', multiplier);
          }
        }
        // check which elements of the
        // array have a perfect division
        // with the product
        // and push the boolean results in a array,
        let booleans = [];
        for (j = 0; j < newArray.length; j++) {
          booleans.push(product % newArray[j] === 0);
        }

        // count the elements that are true
        let trueValues = 0;
        for (let k = 0; k < booleans.length; k++) {
          if (booleans[k] === true) {
            trueValues++
          }
        }

        console.log(booleans);
        console.log('trueValues', trueValues);
        console.log('product', product);


        console.log(iterate);
        // if all elements are true, stop iteration.
        if (trueValues === newArray.length) {
          iterate = false;
        }

        return product;

      }

      let result = findCommon(numbers);

      return result;
    }

    console.log(smallestCommons([1, 5]));

#4

@fooTios, your code has some serious issues:

  1. Immutability of function arguments (aka pure function) - never change value of your argument inside function
  2. Very inaccurate usage of var and let, this is how they have to be used:
var arr = [];
for (let i = 0; ...)

…and not the otherwise, especially if you use i more then once.


#5

Thanks for the comments. :slight_smile:
The code is changed.


#6

Finally it passes all the tests on Atom - chrome but it doesn’t pass the last two tests, in FCC.
Would you like to have a look?

    function smallestCommons(arr) {

      let newArr = arr.sort((a, b) => a - b);

      // get the numbers between the two elements
      let numbers = [];
      let firstElement = newArr[0]
      let secondElement = newArr[1];
      for (let i = 0; i < secondElement; i++) {
        while (firstElement <= secondElement) {
          numbers.push(secondElement--)
        }
      }
      console.log(numbers);


      // find the smallest common perfect divisor
      function findCommon(array) {

        let newArray = [...array]
        let multiplier = newArray[0];
        let product = 0;
        let booleans = [];

        for (let i = 0; i < newArray.length; i++) {
          booleans.push(false)
        }

        // Multiply the first element with multiplier
        // and store the product.
        // Check the product with each value from the
        // inBetweenArray, for a perfect division.
        // Increment the multiplier and check again.
        // In every iteration remover the first value from
        // the inBetweenArray and add the result of the
        // new check at the end (FIFO).
        // If all values are true break the booleans loop
        // If all values are true break the outer loop.

        for (;;) {
          product = newArray[0] * multiplier;
          //  console.log('product', product);
          //  console.log('multiplier', multiplier);
          for (let i = 0; i < newArray.length; i++) {
            //  console.log('newArray', newArray[i]);
            //  console.log('1', booleans);
            booleans.shift()
            booleans.push(product % newArray[i] === 0);
            //console.log(booleans);
            let pass = booleans.every(x => x === true)
            //  console.log('pass', pass);
            if (pass) {
              break;
            }
            //    console.log("booleans", booleans);
          }
          let pass2 = booleans.every(x => x === true)
          if (pass2) {
            break;
          }
          //  console.log('2', pass2);
          multiplier++
        }
        return product;
      }
      return findCommon(numbers);;
    }

#7

See here:


#8

Some other remarks:

1
Instead of for (;;) it’s simpler to use while(true)

2
arr.sort is done “in place” and you’re not using arr anymore so I’d just do:
arr.sort((a, b) => a - b); and not assign it to a new variable.

3
In these two loops i only ever has the value 0. You can make that one loop.

for (let i = 0; i < secondElement; i++) {
    while (firstElement <= secondElement) {
      console.log(i);
      numbers.push(secondElement--);
    }
  }

4
I think it’s a bit strange you create a function inside of another function (findCommon) and then call that function exactly one time. I’d say that a more common pattern is to have other functions beside each other. Unless there’s a good reason not to.

The thinking behind this: if you have a function B within a function A, each time you call A function B is _re_created, which in this case is not necessary.

5
The booleans array does not have a “semantic” name. It is an array of booleans, but what does it mean? What does it represent? That’s the name you should give to the variable (imho).

6
I see some places in your code where you’re pushing and then shifting an array (like booleans).
What you’re doing is making a list of “this number divides cleanly, that number too, that number too” etc…
A simpler solution would be to make an empty array and then push the booleans onto it:
dividesCleanly.push(product % newArray[i] === 0);

Even more simple:
Loop over the checks (whether it divides cleanly) and at the first check that fails (does not divide cleanly) exit the loop. You’re not interested if even one number does not divide cleanly so whether any others do is not interesting.


#9

Thank you very much for your help.
I made all the changes you suggested, except the last one. The problem is that the code checks all the numbers again again. So e.g. in the first iteration 5 and 1 will divide cleanly so I will have 2 trues. Then in the second iteration 5 and 1 will be again true so I will have 4 trues, but not the ones I want… So I get false output. This is why I do the unshift,so eventually the first trues of 1 and 5 etc will be gone and the iteration will stop only if all numbers are checked true in a row. I’m sure you get what I mean, despite my poor explanation.

So the code still doesn’t pass. Maybe I will try to multiply the second number too, as suggested in the hints.

Now that’s strange. It passes the last, but not the second last. And that everywhere, not only in FCC.
Here is the code:

function smallestCommons(arr) {

      arr.sort((a, b) => b - a);

      // get the numbers between the two elements
      let inBetweenNums = [];
      for (let i = arr[0]; i >= arr[1]; i--) {
        inBetweenNums.push(i)
      }
      console.log(inBetweenNums);


      // find the smallest common perfect divisor



      let multiplier = 2;
      let product = 0;
      let dividesCleanly = [];

      for (let i = 0; i < inBetweenNums.length; i++) {
        dividesCleanly.push(false)
      }

      // Multiply the first element with multiplier
      // and store the product.
      // Check the product with each value from the
      // inBetweenNums, for a perfect division.
      // Increment the multiplier and check again.
      // In every iteration remover the first value from
      // the inBetweenNums and add the result of the
      // new check at the end (FIFO).
      // If all values are true break the dividesCleanly loop
      // If all values are true break the outer loop.

      while (true) {
        product = inBetweenNums[0] * inBetweenNums[1] * multiplier;
        //  console.log('product', product);
        //  console.log('multiplier', multiplier);
        for (let i = 0; i < inBetweenNums.length; i++) {
          //  console.log('inBetweenNums', inBetweenNums[i]);
          //  console.log('1', dividesCleanly);
          dividesCleanly.shift()
          dividesCleanly.push(product % inBetweenNums[i] === 0);
          //console.log(dividesCleanly);
          let pass = dividesCleanly.every(x => x === true)
          //  console.log('pass', pass);
          if (pass) {
            break;
          }
          //    console.log("dividesCleanly", dividesCleanly);
        }
        let pass2 = dividesCleanly.every(x => x === true)
        if (pass2) {
          break;
        }
        //  console.log('2', pass2);
        multiplier++
      }
      return product;

    }

    console.log('result', smallestCommons([23, 18]));

#10

Another case that is not correct with your code, and that’s probably easier to debug is smallestCommons([1,7]) your code says the LCM is 210, but 210/4 = 52.5.

I’ll take a more in-depth look right now.


#11

You’re doing great!

I found the problem in your code:
You reuse the dividesCleanly array when changing the multiplier, but you forget to “reset” it.
You can reset it (by setting all values to false).


That being said, and I’m sort of repeating myself here, your solution with dividesCleanly is both more complex and less efficient than necessary.

If you loop over the potential LCM numbers, you can stop as soon as you find that one of the “divisors” does not cleanly divide.

A concrete example:

Let’s say we’re trying to find the LCM for [1,7]. When we’re looking at potential LCM 210 we see that it divides cleanly by 7, 6, 5. But when we find out it does not divide cleanly by 4 (210/4 = 52.5) we no longer need to check 210/3 and 210/2.

See this codepen: https://codepen.io/niels_bom/pen/rqvqOq?editors=0011#


#12

I have no words to thank you man. It works like a charm. :wink:
This is the snippet:

  while (true) {
        product = inBetweenNums[0] * inBetweenNums[1] * multiplier;
        for (let i = 0; i < inBetweenNums.length; i++) {
          if (product % inBetweenNums[i] !== 0) {
            dividesCleanly = false;
            break;
          }
          dividesCleanly = true;
        }
        if (dividesCleanly) {
          return product
        } else {
          multiplier++
        }

#13

Cool! You’re welcome!

I think you can mark the question as solved then, somehow? (I’m relatively new to the FCC forums)


#15

I only had to mark the check icon on the last comment. And it gives a Solution check! Thanks again.

Anyway, because I didn’t try to solve the problem at first place as you suggested and I kinda got the solution from a snippet you gave me, I couldn’t leave it like this. I kept thinking that I got lazy and that I just wanted this to finish and go to next challenge.

But this is not a good habit. I’m here to learn not to pass challenges. So I though I should give it a try to replace the while (true) loop with a do - while loop.

After some time, I got it, and more importantly, I understand how it works.
But to be honest, I took the while (i !== inBetweenNums.length) from the FCC solution. I couldn’t find a way to stop the loop. Even though it’s so obvious. Like, stop the loop when you finally get to iterate through all numbers, which means you didn’t break anywhere, so all are clean.
Here is the snippet:

    do {
        product = inBetweenNums[0] * inBetweenNums[1] * multiplier;
        //  console.log('prod... ', product);
        for (i = 0; i < inBetweenNums.length; i++) {
          console.log('1.. ', i);
          if (product % inBetweenNums[i] !== 0) {
            //  console.log(inBetweenNums[i]);
            break;
          }
        }
        multiplier++

        console.log('1.. ', i);
      } while (i = inBetweenNums.length)
      //  console.log(product);
      return product
    }


#17

I’m here to learn not to pass challenges.

This is a great attitude! Really nice to see that :slight_smile:

It actually took me some hours to think of a more efficient solution. Not so much in how to write the code, but the mathematical part of it, which is not my strong point.

Here’s my final solution: https://codepen.io/niels_bom/pen/pxLKYX
I added some code to see how many “checks” I do, so I could measure how efficient the code is.
There’s some recursion in there as well.

I think I can make the code even more efficient by ignoring the “factors” of the divisors I check with. But I haven’t made that yet. It’s probably also a good idea to have some better metrics around my code.

Oh and about while vs do while. I actually almost never use do while, I like while(true) and break more. Functionally it’s the same.

Have a nice weekend!


#18

A nice weekend to you to bro :wink:


#19

Hi,
Well it took me an hour to fully understand your code.
The funny thing is that in freecodecamp solutions, they say
that the perfect divisor of the largest numbers is more likely to be the
smallest common multiple.
So I wanted to check it out and I used the reverse() function that you commented out.
And by my surprise it seems that we do less checks if we start with
the smallest ones.
Checks with smallest = 702
Checks with largest = 1455

May be it has to do something with this

// For efficiency we make use of the following fact:
// scm
// for [1, 2, 3, 4, 5, 6, 7] is a product
// of scm
// for [1, 2, 3, 4, 5, 6] and X
// 420 == > 60 * X
// This means we only have to check 60, 120, 180 … 420.

I do have some more comments, and questions, if you want to check it out:
Here is the code:


#20

I wanted to double check, so I went back to the challenge, and I checked there too.
For numbers 1 - 5, I get 1 check for large and 8 for small. Well I did skip the 1.
:roll_eyes:

So why is that? Have I done something wrong when checking your code for the largest ones?

Here is the code.
I have both cases, in one. I just comment out each case per try.