Tell us what’s happening:
Hi everyone,
I have been trying to get Least Common multiple. I have been doing this by sorting and then expanding array between two extreme values. After that I just used the while loop to bring the value to the wanted condition. It works well for until I try higher values - the code returns random values between 726541 - 796605 each time I refresh. Can somebody explain this weird behavior? Thanks
function smallestCommons(arr) {
arr = arr.sort((a,b) => a-b);
console.log(arr);
console.log(arr[arr.length-1]-arr[0]);
var arrLay = [];
for (let i = arr[0]; i<=arr[arr.length-1]; i++){
arrLay.push(i);
}
console.log("arrLay = " +arrLay);
let mult = arrLay[0];
while(arrLay.every( (item) => mult% item === 0) === false){
mult++
}
console.log(mult);
return mult;
}
smallestCommons([23,18]);
Your browser information:
User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.103 Safari/537.36 OPR/60.0.3255.109.
I don’t know where to reference you, but it is about the number of steps needed, your code raise a variable by one and then do multiple checks on it, that’s that need refactoring.
I remember Khan Academy having something on time complexity but can’t find it
I struggled a bit on this one to start - mostly because it was a surprisingly deep challenge that more resembled a project. However I sketched abrute force solution in a post yesterday:
Are you familiar with:
Sieve of Eratosthenes for finding prime numbers?
Are you familiar with prime factorization?
Do you realize that the *prime factorization of each number is unique?
Hopefully these hints at the math behind this problem, and solution, help out.
There is a simpler efficient algorithm that doesn’t require prime factorization of the input range.
Write a Greatest Common Divisor function GCD(a,b).
Note that the Smallest Common Multiple (SCM) of any two numbers a and b is the value: a * b / GCD(a,b).
Calculate the SCM for the first two numbers of the range; then successively calculate the SCM for that value plus the next value in the range until you hit the end of the range.
This is far more efficient than a simple integer loop, yet only 1/2 or 1/3 as much code as my earlier prime-factorization algorithm.