Smallest Common Multiple - what does reduce do in this solution?

I had quite a bit of trouble with this challenge and I’ve been going through the solutions to see how they all work. I can’t figure out how reduce is used in the GCD/LCM solution (code below).

With the reduce method being called on range, I just don’t know how it ends up returning the LCM of all the numbers in the range.

If anyone can provide a quick explanation I would really appreciate it. Thanks!

function smallestCommons(arr) {
  // Setup
  const [min, max] = arr.sort((a, b) => a - b);
  const range = Array(max - min + 1)
    .fill(0)
    .map((_, i) => i + min);
  // GCD of two numbers
  // https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm
  const gcd = (a, b) => (b === 0) ? a : gcd(b, a % b);
  // LCM of two numbers
  // https://en.wikipedia.org/wiki/Least_common_multiple#Using_the_greatest_common_divisor
  const lcm = (a, b) => a * b / gcd(a, b);
  // LCM of multiple numbers
  // https://en.wikipedia.org/wiki/Least_common_multiple#Other
  return range.reduce((multiple, curr) => lcm(multiple, curr));
}

smallestCommons([1, 5]);

you need to return the lcm of al numbers in a range

mathematical explanation first
(not with a range, but to make it fast and easy)
if you have 2 5 and 6, you can get the lcm first of the first two numbers, 2 and 5 have a lcm of 10, and then you can get this and calculate the lcm with the next number, and the lcm between 6 and 10 is 30, which is also the lcm of 2, 5 and 6

what the reduce does is calculate the lcm of the first two numbers, the the result of that with the next and so on
at the end you get the lcm of all numbers

2 Likes

One thing to keep in mind is that when no initial value is provided for a reduce, the first value in the array is used instead. So the reduce computes the lcm of the first two entries, then the lcm of the result and the third entry, then the lcm of that result and the fourth entry, and so on. This reduce therefore follows the formula in the Wikipedia article in the comment.

I think it’s worth noting that this solution is short/terse, but there is a lot of complex math going on behind the scenes.

1 Like

@ieahleen @JeremyLT thanks a lot for the explanations, that all makes sense now. I didn’t know that mathematically the LCM of 2 and 5 (being 10) could then be compared with the next number. Knowing that makes it clear how the reduce works here.

1 Like