Solution to challenge (smallest common multiple)

Contributors
1

Link to guide: freeCodeCamp Challenge Guide: Smallest Common Multiple

Solution:

const smallestCommons = (arr) => {
  let primeFactors = {};
  for (let i = Math.max(Math.min(...arr), 2); i <= Math.max(...arr); i++) {
    let primes = getPrimeFactors(i);
    for (let j in primes) {
      if (!primeFactors[j] || primes[j] > primeFactors[j]) {
        primeFactors[j] = primes[j]
      }
    }
  }
  let result = 1;
  for (let i in primeFactors) {
    result *= i ** primeFactors[i]
  }
  return result;
}

const getPrimeFactors = (num) => {
  const primes = {};
  for (let factor = 2; factor <= num; factor++) {
    while ((num % factor) === 0) {
      primes[factor] = (primes[factor]) ? primes[factor] + 1 : 1;
      num /= factor;
    }
  }
  return primes;
}
smallestCommons([1,5]);

Theory:

Another way to calculate the least common multiple of any set of numbers is to first break the numbers down into their prime factors. So, for example, if you have the set of numbers [30, 45, 56], their prime factors would be:

30 = 2 × 3 × 5
45 = 3 × 3 × 5
56 = 2 x 2 x 2 x 7

Now to get the least common multiple, just find the greatest number of times each factor occurs between the numbers. So for the above example, for the factor 2, it occurs only once in 30, but three times in 56, so we use the number 3. Likewise in 45 we have two 3’s, in 30 and 45 we have one 5 (so the most it occurs in any number is one), and in 56 we have one 7. So to calculate the lowest common multiple (lcm) for these three numbers, we just multiply them all out:

lcm([30, 45, 56]) = 2 x 2 x 2 x 3 x 3 x 5 x 7 = 2520

Code Explanation:

  • Loop through the numbers between the two values given (with a minimum of 2 since 1 cannot be broken down into prime factors).
  • For each number find the prime factors.
  • If the number of occurrences of any factor is greater than what we have from previous numbers, add or save this to the primeFactors object.
  • Loop through the primeFactors object and multiply all of the number out to the power of the number of their respective occurrences.
2 Likes
2

The math looks right on this. If be curious about how this compares to the performance of using the GCD, as factorization can be expensive.

3

@JeremyLT It looks like GCD is about 3-5 times faster than this method (https://codesandbox.io/s/elastic-moore-mmqn5). However for me with large ranges (e.g. 1-300), the stack size is exceeded, whereas with the prime factor method it can handle 1-10000 (above which I get an infinite loop warning trigger), however the result is infinity for anything much greater than 1-700 (which I guess means that it exceeds the maximum integer size).

So basically the prime factor method is memory efficient whereas the GCD method is processor efficient.

1 Like
4

I think you can avoid the stack size limit with

  function gcd(x, y) {
    // Implements the Euclidean Algorithm
    while (y !== 0) {
      [x, y] = [y, x % y];
    }
    return x;
  }

but you have to bully codesandbox into ignoring the loop iteration count.

I’d expect the GCD method to require less storage and be more memory efficient. Preallocation of the prime factors array might help efficiency.

5

Here’s my solution. I found the Math on stackoverflow. But I improved upon that initial solution to make it work with an array starting either with a lower or a higher number.
Also, all the code in ES6 wich is pretty cool :slight_smile: .

function smallestCommons(arr) {

const gcd = (a, b) => b == 0 ? a : gcd (b, a % b);
const lcm = (a, b) =>  a / gcd (a, b) * b;
const lcmAll = (ns) => ns.reduce (lcm, 1);
const rng = (lo, hi) => [...Array(Math.abs(hi - lo) + 1)] .map ((_, i) => hi>lo ? lo+i: hi+i);
const lcmRng = (lo, hi) => lcmAll (rng (lo, hi));

return(lcmRng(arr[0],arr[1]));
}

smallestCommons([23,18]);

Source: https://stackoverflow.com/questions/31302054/how-to-find-the-least-common-multiple-of-a-range-of-numbers

12

@multiwebinc, sorry for the slow review, but I’ve added your writeup as a solution. Thank you for your contribution!

2 Likes
13

I took a much less efficient approach…kind of using a hammer :grinning:
I basically create the range between the two numbers provided, and start checking from the higher number in the range if this number can be perfectly divided by all numbers in the range. In case not, I increase the number I test until it satisfy the condition.
I don’t know how to test the efficiency of this approach…but it works and it’s easy to understand!

function smallestCommons(arr) {
  let ext = [...arr].sort((a,b) => a - b);
  let testRange = [];
  let i = ext[0];
  while (i <= ext[1]) {
    testRange.push(i);
    i++;
  }
  let res = ext[1];
  while (true) {
    if (testRange.every(item => res % item == 0)) {
      return res;
      break
    }
    res++;
  }
}
14

If you want to suggest a solution to be added in the guide, please open a new solution suggestion thread. Please do not share your solution for the sake of sharing it though, as we are trying to cut back on the number of spoiler solutions on the forum.

Thank you for understanding.