Smallest Common Multiple solution -efficient enough?

JavaScript
1

Hi,
I wonder if someone could give me feedback on my solution. It passes all the tests apart from the last one, and from other posts on this challenge I get the impression that this is about the solution not being efficient enough.

I’ve done coding before but have never been good at maths. How can I improve the solution? It doesn’t depend on an array, which I think is good because no potentially large array of numbers needs to be held in memory (depending on what you input), but perhaps the algorithm isn’t efficient enough if it’s not passing the last test.

(I also read that you can add // noprotect to get the last test passing, but this doesn’t work for me in any case).

[spoiler]```js

// noprotect
function smallestCommons(arr) {
let low, high, result, isNotMultiple;
[low, high] = arr.sort((a,b) => a-b);
result = high * 2;

do {
isNotMultiple = false;
for (let i = low; i <= high; i++) {
if (result % i !== 0) {
isNotMultiple = true;
result += high;
break;
}
}
} while (isNotMultiple)

return result;
}

smallestCommons([1,5]);


**Browser information:**

User Agent is: Firefox 60.0, Windows.

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

actually it is not very efficient that is why last test case is not passing ,In last test case loop will run around 263340 times until the multiple is found according to your code.
otherwise logic is great just a little optimisation is needed.

1 Like
3

Would it be more efficient if he finds the next common multiple rather then multiplying the high number of results for each loop?

4

So spoilers here; I am not very knowledgeable w/r/t maths, so had to look this up, but:

  1. lowest common multiple of a and b (make it a function like lcm(a, b)) is equal to a times b divided by the greatest common divisor of a and b.
  2. So this looks like (a * b) / gcd(a, b).
  3. GCD is very easy to calculate:
    function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}
    (nb the [a, b] = [b, a] is an easy way to swap variables without using a temporary variable, I just used it to save space)
  4. Now, if you have a range of numbers low…high, you can just run the lcm function on the first two, then take the result of that and run it on that and the next number and so on. In other words, reduce.
function smallestCommons(arr) {
  return inclusiveRange(Math.min(...arr), Math.max(...arr)).reduce(lcm);
}

function inclusiveRange(a, b) {
  const range = [];
  for (let i = a; i <= b; i++) {
    range.push(i);
  }
  return range;
}

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b)
}

The performance will never be fantastic because the number of computations just explodes as you add more numbers to the range, but I think it should be pretty good - passes the tests no problem, and there’s no visible slowdown when I run the function in my browser.

Edit:

6 Likes
5

Thanks so much for this Dan : - )