freeCodeCamp Challenge Guide: Smallest Common Multiple

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.

3 Likes

You can do it yourself.

4 Likes
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;
}
23 Likes

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]);
2 Likes

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

18 Likes

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;  
}
63 Likes
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.

2 Likes

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.

1 Like

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]);

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]);

Simple and elegant. Well done

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

8 Likes

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]);

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.

3 Likes

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

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)

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;
    } 
  });
}
5 Likes

Indeed, it quickly reaches Infinity.
To have an idea of the size of the number, you can do something like that :

var numberOfZero = 0;
Object.keys(factors).forEach 
(
    function(key) { numberOfZero += Math.log10( Math.pow(key, factors[key]) ); } 
); 

It will count the number of zero of the final number.

Not as good as others but this is what i came up with.

function getRange(arr) {
  var range = [];
  arr = arr.sort();
    for (i=arr[0]; i<= arr[1]; i++){
        range.push(i);
    }
  return range;
}

function getPrimeFactors(n) {
  var factors = [];
  for (var i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      var count = 0;
      while (n % i === 0) {
        n = n / i;
        count++;
      }
      for (var j = 1; j <= count; j++) {
        factors.push(i);
      }
    }
  }
  if (n !== 1) {
    factors.push(n);
  }
  return factors;
}

function getLCMFactors (arr) {
  // return all the LCM factors
  return arr.reduce(function(a,b){

    for(var i=0;i<a.length; i++) {
      // checks if the first value of the first array exists in the following array
        if (b.indexOf(a[i]) !== -1) {
          // if it exists remove that value from the second array and repeat the process
          b.splice(b.indexOf(a[i]), 1);
        }

      }
  // take the first array and combine with the newly filtered array b
      return a.concat(b);

  });
}


function multiply(a){
  var result = 1;
  for (i=0; i<a.length;i++){
    result = result * a[i];
  }
  return result;
}



function smallestCommons(arr) {
  var range = getRange(arr);
  var AllFactors = [];
  for(var i = 0; i < range.length; i++) {    
  AllFactors.push(getPrimeFactors(range[i]));
}
  var LCMFactors = getLCMFactors(AllFactors);
  return multiply(LCMFactors);
  
  
}


smallestCommons([1,5]);

My solution:

function smallestCommons(arr) {
  //noprotect
  
  //sort array first. so lower comes first
  arr = arr.sort(function(a,b){ return a>b; });
  //create range array 
  var range = []; var start = arr[0]+1;
  while(start < arr[1]){ range.push(start++);}
  
  var count = 1; var flag = true; 
  var common; var rangeCount;
  
  //increment count by one before we find common multiple
  while(flag){
    rangeCount=0;
    if(count % arr[0] === 0 && count % arr[1] === 0){ //common multiple found, assyign it to commont variable
      common = count;
    }
    //Now loop through the range array and check if our common multiple is divided to all of them evenly
    for(var i = 0; i < range.length; i++){
      if(common % range[i] === 0){
        rangeCount++;//count every match
      }
      if(rangeCount === range.length){//if all match, set while flag to false, 
        //we found commont multiple that is evenly divided by sequential numbers in the range
          flag = false;
      }
    }
    count++;
  }
  
  return common;
}

//test
smallestCommons([23, 18]);