Smallest Common Multiple - fails last two use cases

Smallest Common Multiple - fails last two use cases
0

#1

Tell us what’s happening:
My code running in Firefox gives correct results for all use cases

When i run in the Code Camp window, the last 2 use cases fail! I have been staring at this for hours:) - looking for some fresh eyes please

Your code so far


function smallestCommons(arr) {
 // sort into ascending sequence
	arr.sort((a,b)=> a - b);
// create array of numbers to test division
	let rangeArr=[];
	for (let i = arr[0]; i <= arr[1]; i++) {
		rangeArr.push(i);
	}
// set inital values
	let foundDivCM=false;
	let n1CM=arr[0];
	let n2CM=arr[1];
// find divisible CM 
	while (!foundDivCM) {
// find next common multiplier	
		while (n1CM!==n2CM) {
			if (n1CM<n2CM) {
				 n1CM+=arr[0]; 	
			} else {
				n2CM+=arr[1];
			};
		};	
// Check if all numbers are divisible for CM
		let allDivisible=true;
		for (let k = 0; k<rangeArr.length; k++) {
				if (n1CM%rangeArr[k]!==0) {
				allDivisible=false;
				n2CM+=arr[1];
				break;}; 
				};
// If all divisible, return 
		if (allDivisible){console.log(n1CM);return n1CM;};	
 	};
 
  return arr;
}


smallestCommons([1,5]);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:61.0) Gecko/20100101 Firefox/61.0.

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


#2

Hi,
If your program loops excessively the test on FCC will terminate. The assumption is that you have accidentally created an infinite loop (yours does not). Even so, this is a warning that your function is taking too many steps to solve this problem.

This is very common on this challenge. If you search on the FCC Javascript forum you will see many past posts seeking help with just the same problem. There will be some good hints at a fix in those posts so that is a search worth your time.

Ultimately you will need to craft a more efficient algorithm that loops fewer times. Without totally tracing your code I would suggest finding ways to eliminate candidates for LCM that could not be mathematically possible - fewer candidates = fewer tests = fewer loops.

If I understand correctly your function tests multiples of the largest number of array as candidate for LCM. Some (most) of those multiples could never be LCM so testing them is an unnecessary loop


#3

thank you

I added some counters to the code and got this image
while the CM numbers are correct, the loops are a little high :grinning:
I will revisit my algorithm!


#4

I tried out your code in another repl (https://stephengrider.github.io/JSPlaygrounds/) and it works fine in all test cases. So it looks like your code is taking too long to execute, even though it completes the final test case in just 5 milliseconds on my computer.

You can make your code faster by incrementing your scm variables by larger valid amounts when they fail:

Increment n1CM by arr[0] * (arr[1] - 1) instead of just arr[0]
Increment n2CM by arr[1] * (arr[1] - 1) instead of just arr[1]

Remember to initialize these variables with these values too.


#5

Thank you for your feedback. I looked at the other forum links and i rewrote the algorithm using Euclids method and LCM calc. it works fine now.

I think the main challenge i faced was coming to the realisation that the actual problem was to solve LCM for the range of numbers not just the first and last!
Once i understood that from the forum posts it became clear that my brute force approach would work up to a point but ultimately was never going to scale up

Again thank you for your help!