freeCodeCamp Challenge Guide: Smallest Common Multiple

Dude! this one is fast!

function smallestCommons(arr) {
  arr.sort();
  var lo = arr[0], hi = arr[1];
  var cm = hi;
  while (cm) {
    for (var range = hi - 1; range >= lo; range--) {
      if (cm % range !== 0) { // this range value didn't divide evenly
        cm += hi;  // so move to the next multiple of the high array number
        break; // and restart the for-loop
      }
      if (range === lo) { // all range values divided evenly
        return cm; // so this must be the common multiple
      }
      // a range value passed, so try the next one down
    }
  }
}
function smallestCommons(arr) {
  arr.sort();                                   
  var arr2 = [];
  var a = arr[0];
  var b = arr[arr.length-1];
  for(var i=1;i<b;i++){
      if((arr[0]+i)<b){
      arr.push(arr[0]+i);
      }
  }
 arr.sort(function(a,b){
     return a-b;
 });
 
for (var i=1; i<Infinity;i++){
   if(arr.every(function(element,index,array){return ((b*i)%element)==0})){
     return b*i;
   }
}
}


smallestCommons([23,18]);

Code takes ton of time for largely spaced numbers tho. 45s for [1,23] :yum:

2 Likes
function smallestCommons(arr) {
 
  var min = Math.min(arr[0],arr[1]);
  var max = Math.max(arr[0],arr[1]);
  var range = [];
  
  for (var x=min; x<=max; x++){
    range.push(x);
  }
  
  var a = Math.abs(range[0]);
  
  for(var i=1;i<range.length;i++){
    var b = Math.abs(range[i]);
    var c = a;
    
    // if "a" and "b" > 0 return true, else return false
    while(a&&b){
      if(a>b){
        a %= b;
      } else {
        b %= a;
      }
    }
    a = Math.abs(c * range[i] / (a+b));
  }
  return a;
}


smallestCommons([1,5]);

// It was very hard, I can't do this lesson alone. I saw a video on YouTube
// https://www.youtube.com/watch?v=itPtMtdEPis&t=604s
1 Like

Here is my code which almost crashed my browser and took 263339 iterations.

function smallestCommons(arr) {
  arr.sort((a,b)=>a-b);
  var Fullarr=Array.from({length:arr[arr.length-1]+1},(v,i)=>i).slice(arr[0]).sort((a,b)=>b-a);
  function sc(a){
    return k%a===0;
  }
  var i=1;
  var k=arr[arr.length-1];
  console.log(Fullarr.every(sc));
  while (Fullarr.every(sc)!==true){
    Fullarr.every(sc);
    console.log("i="+i);
    //console.log("j="+j);
    console.log("k="+k);
    i++;
    k=arr[arr.length-1]*i;
  }
  return  k;
}



smallestCommons([23,18]);

after studying the intermediate solution i have modified it a little now number of loops half than previous one, so I guess intermediate solution is more faster?

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

    var lcm = range[0];
   
    for (i = 1; i < range.length; i++) {

	var GCD = gcd(lcm, range[i]);
	console.log("i="+i+" lcm="+lcm+" range[i]="+range[i]+" GCD="+GCD);
	lcm = (lcm * range[i]) / GCD;
 if(range.every(sc)){break;}
}
  return lcm;
	
	function sc(element){
    return lcm%element===0;
  }
    
    function gcd(x, y) {	// Implements the Euclidean Algorithm
	if (y === 0)
	    return x;
	else
	    return gcd(y, x%y);
    }
}

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

Can you explain your solution please? I find it elegant and relatively simple.

2 Likes

Hello guys!

Man this was hard ! I couldnā€™t wrap my head around this challenge. After Iā€™ve done some reading and finding some mathematical examples of Euclidā€™s Algorithm, it was just a matter of translating the math into JS code which I think looks clean and easy to understand. Iā€™ve seen some of you used the Euclidean Algorithm approach and worked fine for your code. This is mine:

    function smallestCommons(arr) {
      
      var max = Math.max(...arr),
          min = Math.min(...arr),
          range = [],
          scm; // smallestCommonMultiple
      
      for (var i = min; i <= max; i++) {
        range.push(i);
      }
      function gcd(a, b) {  // greatestCommonDivisor based on Euclid's Algorithm
        var answer;    
        for (var x = 0; x <= a; x++) {
          if(a % x === 0 && b % x === 0)
            answer = x;  
        }
        return answer;
      }
      function lcm(a, b) {  // leastCommonMultiple based on Euclid's Algorithm
        return (a * b) / gcd(a, b); 
      }
      scm = range.reduce(lcm);   
      
      return scm; // smallestCommonMultiple
    }
smallestCommons([23, 18]);
5 Likes