freeCodeCamp Challenge Guide: Smallest Common Multiple

camperbot · May 27, 2020, 4:39am

Smallest Common Multiple

Problem Explanation

The smallest common multiple between two numbers is the smallest number that both numbers can divide into. This concept can be extended to more than two numbers as well.

We can first start with just finding the smallest common multiple between two numbers. Naively, you can start writing out multiple of each number until you write a multiple that exists from both numbers.

An example would be the numbers 3 and 4. The multiples of 3 are 3, 6, 9, 12, 15, 18, ... and the multiples of 4 are 4, 8, 12, 16, 20, .... The first smallest number we run into in both lists is 12 so this is the smallest common multiple between 3 and 4.

This problem can be confusing because most people look for the smallest common multiple of just the two numbers but forget the keyword range. However, this means that if you are given [1,5], then you have to check for the smallest common multiple for all the numbers [1,2,3,4,5] that is evenly divisible by all of them.

Relevant Links

Least (Smallest) Common Multiple

Hints

Hint 1

Create an array with all the numbers that are missing from the original array to make it easier to check when having to check for even division.

Hint 2

You can use remainder operator (%) to check if the reminder of a division is 0, which means it is evenly divisible.

Hint 3

If you sort the array from greatest to smallest, then you can use the first two numbers as a first check for the smallest common multiple. This is because they are more likely to be the smallest common multiple than the lower numbers.

Solutions

Solution 1 (Click to Show/Hide)

function smallestCommons(arr) {
  // Sort array from greater to lowest
  // This line of code was from Adam Doyle (http://github.com/Adoyle2014)
  arr.sort(function(a, b) {
    return b - a;
  });

  // Create new array and add all values from greater to smaller from the
  // original array.
  var newArr = [];
  for (var i = arr[0]; i >= arr[1]; i--) {
    newArr.push(i);
  }

  // Variables needed declared outside the loops.
  var quot = 0;
  var loop = 1;
  var n;

  // Run code while n is not the same as the array length.
  do {
    quot = newArr[0] * loop * newArr[1];
    for (n = 2; n < newArr.length; n++) {
      if (quot % newArr[n] !== 0) {
        break;
      }
    }

    loop++;
  } while (n !== newArr.length);

  return quot;
}

// test here
smallestCommons([1, 5]);

Code Explanation

Because of the possibility of the smallest common denominator being among the two biggest numbers, it makes sense to check those first, so sort the array.
Create a new array to sort all the numbers, newArr.
Use a descending for loop (var i = arr[0]; i >= arr[1]; i--) to add the numbers from the biggest to the smallest in the new array.
Declare the variables for the quotient so we can access them outside the loop:
- the quotient that’ll be our smallest common multiple (quot)
- the loop number we’re checking (loop)
- the index of the array of numbers (n)
Use a do whileloop to check what we need whilen is not the same length as the new array.
In the do part, we are going to multiply the very first number, times the number of loops, times the second number (quot = newArr[0] * loop * newArr[1];).
The loop part will allows us to increase the number we’re checking beyond the greatest number we have without having to change the algorithm.
We enter a for loop that will go from n being 2 and going up by one (loop++) while it is smaller than the array with all the numbers (n < newArr.length).
If the quotient does not divide evenly (quot % newArr[n] !== 0), then stop the loop (break;). If it is even, then check for the next elements (n++) in the array until it is not even or we find our answer.
Outside the loop, increase the value of loop (loop++).
At the end of the loop return the quotient (return quot;).

Note: If the array only has two elements, then the for loop never gets used and the return value is the product of said numbers.

Relevant Links

Solution 2 (Click to Show/Hide)

function smallestCommons(arr) {
  var range = [];
  for (var i = Math.max(arr[0], arr[1]); i >= Math.min(arr[0], arr[1]); i--) {
    range.push(i);
  }

  // can use reduce() in place of this block
  var lcm = range[0];
  for (i = 1; i < range.length; i++) {
    var GCD = gcd(lcm, range[i]);
    lcm = (lcm * range[i]) / GCD;
  }
  return lcm;

  function gcd(x, y) {
    // Implements the Euclidean Algorithm
    if (y === 0) return x;
    else return gcd(y, x % y);
  }
}

// test here
smallestCommons([1, 5]);

Code Explanation

The first, basic solution requires over 2,000 loops to calculate the test case smallestCommons([1,13]), and over 4 million loops to calculate smallestCommons([1,25]). This solution evaluates smallestCommons([1,13]) in around 20 loops and smallestCommons([1,25]) in 40, by using a more efficient algorithm.
Make an empty array range.
All numbers between the given range are pushed to range using a for loop.
The next block of code implements the Euclidean algorithm, which is used for finding smallest common multiples.

Relevant Links

Solution 3 (Click to Show/Hide)

function smallestCommons(arr) {
  // Euclidean algorithm for the greatest common divisor.
  // ref: https://en.wikipedia.org/wiki/Euclidean_algorithm
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

  // Least Common Multiple for two numbers based on GCD
  const lcm = (a, b) => (a * b) / gcd(a, b);

  // range
  let [min, max] = arr.sort((a, b) => a - b);
  let currentLCM = min;

  while (min < max) {
    currentLCM = lcm(currentLCM, ++min);
  }

  return currentLCM;
}

// test here
smallestCommons([1, 5]);

Code Explanation

Extract minimum and maximum from provided arr by sorting and grabbing the first and last values.
Initialise smallestCommon with the LCM of first two numbers.
Loop through range computing LCM of current LCM and next number in range lcm(a, b, c) = lcm(lcm(a, b), c).

Relevant Links

Prefix increment operator ++

Solution 4 (Click to Show/Hide)

const smallestCommons = arr => {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  // Initially the solution is assigned to the highest value of the array
  let sol = max;

  for (let i = max - 1; i >= min; i--) {
    // Each time the solution checks (i.e. sol%i===0) it won't be necessary
    // to increment 'max' to our solution and restart the loop
    if (sol % i) {
      sol += max;
      i = max;
    }
  }
  return sol;
};

// test here
smallestCommons([1, 5]);

Code Explanation

Extract min and max from arr using Math.min() and Math.max(), respectively. As the arguments to these functions are integers, it is necessary to spread ... the array.
As a first guess, let’s say that the solution is max. (we will increment this value later on if it is not the solution)
Confirm that our solution is a multiple of all the values between max and min using a for loop.
In case it isn’t a solution, increment max to our solution (i.e. get the next multiple of the arr highest value) and restart the loop i = max. Note that it isn’t i = max - 1 since the for loop hasn’t finished yet. Once it is finished, the loop itself will execute i--. It is also worth mentioning now that we started the loop at i = max and decremented i throughout instead of starting at i = min and then increment it in order to minimize the number of iterations.
The if statement never being true means that all numbers between min and max are divisible by our solution

Relevant Links

Rafase282 · August 10, 2016, 2:59am

Rafase282 · August 20, 2016, 8:26pm

samuelpath · September 1, 2016, 10:11am

You forgot the indentation on the intermediate and advanced solution, making them harder to read.
Can I correct this myselft or should I ask you to update it?
Thx again.

Rafase282 · September 1, 2016, 7:12pm

You can do it yourself.

drguildo · December 13, 2016, 11:36am

function smallestCommons(arr) {
  function isValidMultiple(m, min, max) {
    for (var i = min; i < max; i++) {
      if (m % i !== 0) {
        return false;
      }
    }
    
    return true;
  }
  
  var max = Math.max(arr[0], arr[1]);
  var min = Math.min(arr[0], arr[1]);
  var multiple = max;
  
  while (!isValidMultiple(multiple, min, max)) {
    multiple += max;
  }
  
  return multiple;
}

akashkriplani · January 10, 2017, 7:02am

Alternative basic solution:

function smallestCommons(arr) {
  var min = Math.min.apply(null, arr);
  var max = Math.max.apply(null, arr);
  var listOfNum =[];
  while (min<=max){
    
      listOfNum.push(min);
      min++;
  }
  
  var result = listOfNum[0];
  
for (var i = 1; i<listOfNum.length; i++)
    result = findLCM(result, listOfNum[i]);
  
  return result;
}

function gcd(a, b){
  
  while (a !== b){
    
    if(a > b)
      a = a - b;
    else
      b = b - a;
    
  }

  return a; // GCD of two numbers
}

function findLCM(a, b){
  
  return a * (b / gcd (a,b));
  
}
smallestCommons([1,5]);

Cowwy · February 12, 2017, 2:31am

Dang, after reading all these solution. I just realized I tackled this problem the hardest way possible. LOL

JanEgbers · February 23, 2017, 12:11pm

Came up with a short basic solution:

function smallestCommons(arr) {

  var max = Math.max(arr[0], arr[1]);
  var min = Math.min(arr[0], arr[1]);
  var mltple = max;

  for(var i = max; i >= min; i--){
    if(mltple % i !== 0){
      mltple += max; 
      i = max;
    } 
  }

  return mltple;  
}

awb · February 22, 2017, 6:07am

var tester = 0;

function smallestCommons(arr) {
var ultimate = 0;
  arr = arr.sort(function(a, b) {
    return a - b;
  });

  console.log(arr);

  var ranges = Range(arr[0], arr[1]);

  console.log(ranges);

  var first = arr[1];

  var final = first;

  ///function will run here
  recurse(first);

  function recurse(current) {

    var temp = 0;
    var tester = 0;
    for (i = arr[0]; i <= arr[1]; i++) {

      if (current % i === 0) {
        console.log(current + " % " + i);
        tester++;
        console.log(i + " works");
        console.log(tester + " tester");

      } else {

        console.log(i + " broke it");

        var counter = current + first;
        
        console.log(temp + " next run");
        recurse(counter);

        break;
      } //else

      console.log(ranges.length + " is length");

      if (tester === ranges.length) {
        console.log(current);
         ultimate = current;
      }

    } //for

  } //recurse
return ultimate;
} //smallest commons

function Range(a, b) {
  var temrange = [];

  for (i = a; i <= b; i++) {

    temrange.push(i);
  }
  return temrange;
}

smallestCommons([5, 1]);

heres my long and messy code that crashes my browser if the numbers are too big, it works for 1,5 but crashes for 1,13.

shengdzhang · March 13, 2017, 1:06pm

function smallestCommons(arr) {

var maxPrimes = {};

var min = Math.min(arr[0], arr[1]);
var max = Math.max(arr[0], arr[1]);

var primeFactors = function (num) {
    var primeProd = {};
    var factor = 2;

    if (num < 2) {
      return {};
    } 

    while(factor <= num) {
      if(num % factor === 0){
        primeProd[factor] = primeProd[factor] + 1 || 1;
        num /= factor;
      } else {
        factor++;
      }
    }

    return primeProd;
};

//loop through numbers and save the most instance of the prime factors in the main hash 
for(var i = min; i <= max; i++) {
  var temp = primeFactors(i);
  for(var key in temp) {
    if(!(key in maxPrimes) || maxPrimes[key] < temp[key]) {
      maxPrimes[key] = temp[key];
    }
  }
}

var prod = 1;
//loop through main hash to perform multiplication of all prime factors

for(var num in maxPrimes) {
  prod *= Math.pow(parseInt(num), maxPrimes[num]);
}

return prod;

}

Here’s what I ended up. Not optimized. The brute force method that is available right now was inefficient and broke down at [1, 23]. Works by making a hash of prime factors for each number and calculating the SCM through a main hash.

RaneWrites · March 19, 2017, 5:55am

I factored all the numbers in the range and then multiplied them all together.

function smallestCommons(arr) {
  
  var allFactors = { };
  
  var tmpArr = [];
  
  var curNum;
  
  var factorKeys = {};
  
  var count = 0;
  
  var theProduct = 1;
  
  var tmpNum;
  
  if (arr[1] < arr[0]) {
    tmpNum = arr[1];
    arr[1] = arr[0];
    arr[0] = tmpNum;
  }
  
  for (var i = arr[0] > 1 ? arr[0] : 2, l = arr[1]; i <= l; i++) {
    tmpArr = factorMe(i);
    for (var j = 0, l2 = tmpArr.length; j < l2; j++) {
      if (!curNum || curNum != tmpArr[j]) {
        curNum = tmpArr[j];
        count = countNumbers(curNum, tmpArr);
        if (!allFactors[curNum] || allFactors[curNum] < count) {
          allFactors[curNum] = count;
        }
      }
    }
  }
  
  factorKeys = Object.keys(allFactors);

  for (var k = 0, l3 = factorKeys.length; k < l3; k++) {
    theProduct *= Math.pow( factorKeys[k], allFactors[factorKeys[k]] );
  }
 
  return theProduct;
}

function countNumbers(num, arr) {
  var count = 0;
  for (var i = 0, l = arr.length; i < l; i++) {
    if (num == arr[i]) count++;
  }
  return count;
}

function factorMe(num) {
  var factors = [];
  
  var divisor = 2;
  
  while(divisor != num) {
    if ( num % divisor === 0) {
      factors.push(divisor);
      num /= divisor;
    } else {
    divisor++;
    }
  }
  
  factors.push(num);

  
  return factors;
}


smallestCommons([1,5]);

zcabez · March 20, 2017, 6:32pm

I have done it by getting the highest common multiple first then simplify it.

function smallestCommons(arr) {
  var sorted = arr.sort(),
      res = sorted[1],
      multiplier = sorted[1] - 1,
      simplifier = [2, 3, 5, 7],
      leastSearch = true;
 
 // Get the highest common multiple
  while(leastSearch){
    for(var i = sorted[0]; i <= sorted[1]; i++){
      
      if((res % i) !== 0){
        leastSearch = true;
        break;
      } 
      
      leastSearch = false;
    }
    
    if(leastSearch){
      res *= multiplier;
      multiplier--;
    }
    
  }
  
// Simplify the value
  for(var j = 0; j < simplifier.length; j++){
    var canBeSimplified = true;
    var tempRes;
    
    do {
      tempRes = res / simplifier[j];
      for(var x = sorted[0]; x <= sorted[1]; x++ ){
        if(tempRes % x !== 0){
          canBeSimplified = false;
          tempRes = tempRes * simplifier[j];
          break;
        }
      }
      
      res = tempRes;
    } while (canBeSimplified);
    
  }
  
  
  return res;
}


smallestCommons([1, 13]);

aosdab · March 25, 2017, 11:35pm

Simple and elegant. Well done

yodist · March 26, 2017, 1:09pm

Below is how I pass this challenge, fast and simple:

function smallestCommons(arr) {
  var min=arr[0], max=arr[1], temp;
  if (min>max) {temp=min;min=max;max=temp;}
  var a, b, lim=min;
  for(var i=min;i<max;i++) {
    a=lim;
    b=i+1;
    for (lim; lim%b!==0 ;lim+=a);
  }
  
  return lim;
}


smallestCommons([1,5]);

Run Code

chrishdez02 · March 30, 2017, 5:17am

I was able to pass this challenge with this piece of code. Not as efficient as some others I’ve seen here but glad that it works. I’m still new to this whole javascript thing and always looking for ways to make my code more efficient so any feedback is welcome :).

function smallestCommons(arr) {

var newArr = []
var acc = Math.min(…arr);
var firstVal = arr[0];
var secondVal = arr[1];
var boo = 0;

// Sequential Array

 while (acc< Math.max(...arr)+1) {

    newArr.push(acc);
    acc += 1;
  }

while (boo == 0){
while (firstVal != secondVal)
{
if (firstVal>secondVal) {
secondVal += arr[1];
}

        else if (firstVal<secondVal) {    
          firstVal += arr[0];
        }

    }   

  for (i=1;i<newArr.length-1;i++) {

    if (firstVal % newArr[i] != 0) {  
      
      firstVal += arr[0];
      break;  
    }
    else if (i <newArr.length -2){
      continue; 
    }   
 
    else if (i = newArr.length-2) {
      var boo = 1; 
      continue;
    }
}

}

return firstVal;

}
smallestCommons([1,13]);

MagicMixer · April 3, 2017, 10:16pm

Advanced solution.
This code is quite long, and firstly I thought I tackled this problem the hardest way possible, but after some testing I notices it can astonishingly compute the Smallest Common Multiple (SMC) of [1, 5000] in a few seconds…

// Check if value is a prime number
function isPrime (value) {
  
  if(value%2 === 0 && value > 2)
    return false;
  
  var halfValue = (value-1)/2;
  
  for(var i = 3; i < halfValue; i+=2)
    if(value%i === 0) 
      return false;
  
  return true;
}

// Give the prime factorization of a number
function primeFactors (value) {
  var i = 2;
  var factors = {};
  
  while( value >= i ) 
  {
    if( isPrime(i) ) 
    {
      while( value % i === 0 ) 
      {
        value /= i;
        factors[i] = factors[i] ? factors[i] + 1 : 1; 
      }
      i++; 
    }
    else 
      i++; 
  }
  return factors;
}

// Give the highest value of each factor of 2 primes factorization
function addFactors (f1, f2) {
  Object.keys(f2).forEach 
  (
    function(key) 
    {
      if( ( f1[key] || 0 ) < f2[key] )
        f1[key] = f2[key]; 
    } 
  );
  return f1;
}

// Calculate the smallest common multiple
function smallestCommons(arr) {
  var scm = 1;
  var factors = {};
  
  var min = Math.max( Math.min( arr[0], arr[1] ), 2 );
  var max = Math.max( arr[0], arr[1] );
  
  for(var i = min; i <= max; i++) 
  {
    factors = addFactors(factors,primeFactors(i)); 
  }
  
  Object.keys(factors).forEach 
  (
    function(key) {
      scm *= Math.pow(key, factors[key]); 
    } 
  );
  
  return scm; 
}

console.log(smallestCommons([1,5000]));

So how does it works ?

This code is based on the Prime Factorization (PF) of numbers
e.g : 720 = 2x2x2x2 x3x3 x5

Let’s see the PF of the SMC of [1, 9] :

2520 = 2 x 2 x 2 x 3 x 3 x 5 x 7
This can be computed with the function primeFactors(2520), which returns
= > { 2: 3 , 3: 2 , 5: 1 , 7: 1 }

The we do the PF of all numbers from 1 to 9 :

n      2   3   5   7  
---------------------
2    = 1   |   |   |  
3    = |   1   |   |      
4    = 2   |   |   |     
5    = |   |   1   |  
6    = 1   1   |   |  
7    = |   |   |   1   
8    = 3   |   |   |  
9    = |   2   |   |  
---------------------
2520 = 3   2   1   1

We can notice that each value of PF(2520) is the highest value possible in all PF from 1 to 9

The function addFactors return the PF with all the highest possible values.
Then all that is left to do is the inverse of PF.

Fell free to correct / improve my english, it’s quite difficult to explain in another langage.

MaomaoFE · April 20, 2017, 7:41am

I think the product should instand of quot in Basic Code Solution

psychometry · April 29, 2017, 1:36am

I wrote a similar code, but I was only able to calculate up to the hundreds before it give me a null object.

I copied your code to repl.it online coding environment to see if it works as well as you said, but it gave me infinity. I want to know if this is a JavaScript problem or a machine problem that I couldn’t calculate scm(1,5000)

forkerino · May 8, 2017, 6:18pm

I kinda like this:

function smallestCommons(arr) {
  const min = Math.min(arr[0],arr[1]), 
        max = Math.max(arr[0],arr[1]),
        range = [...Array(max+1).keys()].slice(min); 

  return range.reduce(function(a,b){
    for (let i = a; i<=a*b; i+=a){
      if (i % b===0 ) return i;
    } 
  });
}