Smallest Common Multiple - plz help

Tell us what’s happening:
Describe your issue in detail here.

Hi Guys, I’ve been chewing over this problem for a whole day. I haven’t been able to figure out why my function is returning undefined.

I think the problem is something to do with it not updating variables the way I intended. It might be something quite simple that I’ve done wrong. I’d appreciate the community’s help as I’m at a total loss for now.

``````   **Your code so far**
``````
``````
function smallestCommons(arr) {
// setup
let sortedArr = arr.sort((a, b) => a - b);
let seqArr = [];
for (let i = sortedArr[0]; i <= sortedArr[1]; i++) {
seqArr.push(i)
};
console.log(sortedArr);
console.log(seqArr);

// function to check if testNum is divisable by all numbers in the sequence.
// set initial testNum to highest number in the sequence. Set index to 0.
var testNum = seqArr[seqArr.length-1];
console.log(testNum);
var i = 0;
function checkMult(testNum, i) {
// base case - if final number in sequence is reached AND it multiplies into testNum, return testNum.
if ((seqArr[i] === seqArr[seqArr.length-1]) && (testNum % seqArr[i] == 0)) {
return testNum;
// if testNum divides by number in the sequence, look to the next number in the sequence.
} else if (testNum % seqArr[i] == 0) {
var i = i + 1;
return checkMult(scm, i)
// if testNum does not divide by a number, increase testNum by the smallest number in the sequence, reset index and try again.
} else if (testNum % seqArr[i] > 0) {
var testNum = (testNum + seqArr[0]);
var i = 0;
return checkMult(testNum, i);
}
}
}

console.log(smallestCommons([5,1]));
``````
``````   **Your browser information:**
``````

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

Challenge: Smallest Common Multiple

It does not look like you ever call or use the function `checkMult`.

Formatted:

``````function smallestCommons(arr) {
// setup
let sortedArr = arr.sort((a, b) => a - b);
let seqArr = [];
for (let i = sortedArr[0]; i <= sortedArr[1]; i++) {
seqArr.push(i)
};
console.log(sortedArr);
console.log(seqArr);

// function to check if testNum is divisable by all numbers in the sequence.
// set initial testNum to highest number in the sequence. Set index to 0.
var testNum = seqArr[seqArr.length - 1];
console.log(testNum);
var i = 0;
function checkMult(testNum, i) {
// base case - if final number in sequence is reached AND it multiplies into testNum, return testNum.
if ((seqArr[i] === seqArr[seqArr.length - 1]) && (testNum % seqArr[i] == 0)) {
return testNum;
// if testNum divides by number in the sequence, look to the next number in the sequence.
} else if (testNum % seqArr[i] == 0) {
var i = i + 1;
return checkMult(scm, i)
// if testNum does not divide by a number, increase testNum by the smallest number in the sequence, reset index and try again.
} else if (testNum % seqArr[i] > 0) {
var testNum = (testNum + seqArr[0]);
var i = 0;
return checkMult(testNum, i);
}
}
}

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

Thank you Jeremy! I thought someone might spot an obvious error or two. Looks like I also forgot to update one of the previously used var names “scm” to it’s new name testNum.

It now passes the first four criteria, but I now get the following error message which causes it to fail the last two:
RangeError: Maximum call stack size exceeded

I have no idea how to resolve this. Rebuild some leaner code from scratch? Any help would be appreciated.

There are two things you can do.

As a quick fix, you can find a better way to increment `i` (could be a more descriptive variable name, fwiw) so that you cycle through possible numbers more efficiently.

Though, you will get even better performance if you look at this wikipedia page for some more efficient approaches:

specifically the GCD formula and the formula for the LCM of multiple numbers

1 Like

Thanks Jeremy, I tried incrementing by the largest number each time (which on reflection makes a lot more sense) as well as incrementing from high to low (not low to high). Unfortunately though I am still getting the same error.

I think it will probably need reworking to test numbers that are multiples of numbers in the sequence. I am going to have to sleep on this because my brain has been truly defeated.

Hi team, I finally resolved this one and thought I’d share where I was going wrong.

The issue with my first attempt seems to have been in using a recursive function with no pre-determined end point (other than when the result was achieved). I tried more efficient ways of iterating but it wasn’t enough.

I solved this by using a loop instead, with a condition set to the product of all numbers in the sequence (“maxLimit”). I’m not sure how this was computationally any different from the first attempt, but is neater nonetheless.

This was definitely the hardest challenge for me so far but a great learning experience. Here’s the code:

``````function smallestCommons(arr) {
// setup
let sortedArr = arr.sort((a, b) => a - b);
let seqArr = [];
for (let i = sortedArr[1]; i >= sortedArr[0]; i--) {
seqArr.push(i)
};
let maxLimit = seqArr.reduce((a, b) => a * b)

// loop through multiples of the maximum number in the sequence, up to upperBound.
for (let testNum = seqArr[0]; testNum <= maxLimit; testNum = testNum + seqArr[0]) {
// divide each number in the sequence into testNum and +1 to the count each time it divides without remainder.
var count = 0;
for (let j = 0; j < seqArr.length; j++) {
if (testNum % seqArr[j] == 0) {
var count = (count + 1);
}
}
if (count == seqArr.length) {
return testNum;
}
};

}

smallestCommons([5, 1]);

``````

Good. It really feels great when you’re able to solve a challenging problem.

Here are some more ideas to think about.

1. Is sort really necessary? There are exactly two numbers. You just want to find which is the larger. Using sort here obscure the intent. The code becomes clearer by
``````if (arr[0] < arr[1]) {
min = arr[0];
max = arr[1];
} else {
min = arr[1];
max = arr[0];
``````

or

``````if (arr[0] < arr[1]) {
[min, max] = arr;
} else {
[max, min] = arr;
``````
1. I think the `for` loop
``````for (let testNum = seqArr[0]; testNum <= maxLimit; testNum = testNum + seqArr[0]) {
``````

will be more readable if we rewrite it to something like

``````for (let smallestCommonMultiple = max; smallestCommonMultiple <= maxLimit; smallestCommonMultiple += max
``````
1. Is `seqArray` really necessary? You’re using seqArr.length to check whether every number has divided smallestCommonMultiple or not. But do you need an array to test whether every number has divided smallestCommonMultiple or not? The idea is to keep on dividing smallestCommonMultiple from min to max, and if any one of them does not divide it, then we immediately move on to the next possible smallest common multiple. Indeed, we really don’t need to pre-compute maxLimit as we know we will find one by trying the candidates `max`, `2*max`, `3*max`, . . . So we have something like
``````do {
//divide current sCM by num from min to max
//if any num does not divide sCM then no solution yet,
//so repeat the loop with the next possible sCM
//Otherwise, i.e. all num divided current sCM; the solution is found
//current sCM is the solution
``````

We use a Boolean variable and a break statement to implement the logic into actual code.

``````let found;
do {
found = true;
for (/*num from min to max incremented by 1*/) {
if (/*num does not divide smallestCommonMultiple*/) {
found = false;
smallestCommonMultiple += max;
break; //jump out from the for loop
}
}
} while (!found)

``````
1 Like

Though, this is the best approach:
Compute LCM from GCD

LCM of multiple numbers

1 Like