Solved: Smallest Common Multiple challenge

Hey so I believe I have a working solution here - However - the terminal times out too soon, so I cannot pass all of the test cases (5/6 and 6/6)

SOLVED: Removing all console.log statements, freed up memory in the text editor and passed all test cases

function smallestCommons(arr) {
	let max = Math.max(...arr);
	console.log("Max is ", max);
	let min = Math.min(...arr);
	console.log("Min is ", min);
	let count = max;
	let myArr = [];
	while (count >= min) {
		myArr.push(count);
		count--;
	}
	//using reduce find a large common multiple (simple)
	let largeMultiple = myArr.reduce((a, b) => a * b);
	console.log(`largeMultiple: ${largeMultiple}, myArr: ${myArr}`);
	let divisibleNumbers = [];
	//time out issues start here, because the index could be too high
	for (let i = largeMultiple; i > 0; i--) {
		//console.log(i);
		let newArr = [];
		myArr.forEach(e => {
			//console.log(i%e===0);
			newArr.push(i % e === 0);
		});
		//  console.log(newArr);
		if (newArr.indexOf(false) === -1) {
			//console.log(newArr);
			divisibleNumbers.push(i);
			//console.log(divisibleNumbers);
		}
	} //loop
	let smallestMultiple = Math.min(...divisibleNumbers);
  console.log(smallestMultiple);
  return smallestMultiple;

}
//smallestCommons([2, 10]);

SOLUTION:

function smallestCommons(arr) {
	let max = Math.max(...arr);
	let min = Math.min(...arr);
	let count = max;
	let myArr = [];
  //create range
	while (count >= min) {
		myArr.push(count);
		count--;
	}
	//using reduce find a large common multiple
	let largeMultiple = myArr.reduce((a, b) => a * b);
	console.log(`largeMultiple: ${largeMultiple}, myArr: ${myArr}`);
	//time out issues start here, because the index could be too high
	for (let i = 1; i < largeMultiple; i++) {
		let newArr = [];
		myArr.forEach(e => {
			newArr.push(i % e === 0);
		});
		if (newArr.indexOf(false) === -1) {
			return i;
		}
	} //loop
} //function
smallestCommons([1, 5]);

I am moving your thread to #curriculum-help:javascript

Please use the appropriate subforum instead of #general

1 Like

Looping strategies will case you issues because you can get rather high bounds.

I can give you a few pointers to shave off a few loops, but really you should look up these three math ideas on Wikipedia:

  1. How to compute the LCM of multiple numbers
  2. How to compute the LCM with the GCD
  3. How to compute the GCD quickly

Maybe its because ive been working with this all morning, but the Wiki didnt really help…
did you have any pointers to understand how to shave off a few loops :thinking:

It’s been my experience when helping people with this challenge that it’s hard to get a looping solution fast enough (if it is possible).

That said, for the loops I would

  1. Count up to the least common multiple instead of down from this factorial upper bound
  2. Increment by a number bigger than 1 (I can always increment by [fill in the blank] because my final answer must be a multiple of [fill in the blank])

There are some Javascript specific constructs in your code that I can’t really comment on how to speed up because I am a C guy, but there are some small other calculation you can trim.

Ultimately, with this approach you are doing something roughly worse case on the order of n!*n modulo operations but with the GCD approach you can get down to something closer to n*log(n) modulo operations, n multiplies, and n divisions. We can only do so much to fight the very large number of mod operations baked into the looping strategy above.

1 Like

So I actually removed all the console.log statements, and it must have freed up space or memory or something because all the Test Cases passed!!

Which is really great :laughing: :raised_hands:

console.log does take some resources, and generally I/O slows down a script.

1 Like

Can you elaborate some more on this please :eyes:

Printing out statements to the console takes a lot of time. In general, memory movement can become quite expensive, especially in this case where you were writing out to console thousands of times.

I don’t know the exact reasons why this is slow in Javascript, but here is a thread discussing it: https://stackoverflow.com/questions/11426185/will-console-log-reduce-javascript-execution-performance

1 Like