freeCodeCamp Challenge Guide: Smallest Common Multiple

Guide
22

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.

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

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]);
1 Like
25

function check(min,max,x){
for(var i = min; i <=max;i++){
if(x%i!==0) return 0;
}
return 1;
}
function smallestCommons(arr) {
var max=arr[0],min=arr[1];
if(arr[1] > arr[0]){
max=arr[1];
min = arr[0];
}
var mul=min;
var result;
var incre=1;
while(true){
mul=min*incre;
incre++;
if(check(min,max,mul)!==0) {
result=mul;
break;
}

}

return result;
}

26

Erhm, the basic solution does not work when you compile it on the test ! It says ā€œmissing while after do loop bodyā€.

27

What do you mean by indentation ? I canā€™t understand how he can add the good value to ā€œlcmā€

28

In fact after some testing this code came out to be the slowest code, way to slow;
Function #1: 1091ms (your coude)
Function #2: 167ms
Function #3: 223ms
Function #4: 34ms

Your code takes about 32 times longer than the fastest of 4 codes that I tested to do same calculation over 100000 x loop.

var iterations = 100000;
console.time('Function #1');
for(var i = 0; i < iterations; i++ ){
functionOne();
};
console.timeEnd('Function #1')

console.time('Function #2');
for(var i = 0; i < iterations; i++ ){
functionTwo();
};
console.timeEnd('Function #2')
29

My Solutionā€¦
It isnā€™t pretty but it is the fastest one after compared to some other solution in here. I know it can be beautified more but i got tired coming up with this solution and may i will revise it later :wink:

function smallestCommons(arr) {
var max = Math.max(arr[0],arr[1]),
  min = Math.min(arr[0],arr[1]);
  
function commonOfTwo(a, b){  //came up with a function to find the 
for(var i=1; i<=b; i++){     //smallest Common Multiple of 2 numbers
if((i*a)%b===0){
  return (i*a);
  }
 }  
}    
var mltp = commonOfTwo(max,min);
for(var j=min+1; j<max; j++) {    
mltp = commonOfTwo(mltp,j);   //than use the function to iterate 
}                             //through other elements of the range    
return mltp;
}


smallestCommons([1,13]);
1 Like
30

Hello, this is my solution ā€œpre-basicā€:slight_smile:

function smallestCommons(arr) {
var a=[];
var f=0;
var mx=Math.max(arr[0],arr[1]);
var mn=Math.min(arr[0],arr[1]);
for(d=mn; d<=mx; d++){

a.push (d);
}

a.sort(function(a, b) {
return b-a;
});
f=a[0];
while (getF(f, a)!==true) {
f=f+a[0];
}

return f;
}

function getF(f, a) {
var k=0;
a.forEach(function(entry) {
if (f%entry===0) {
}else {
k=1;
}
});

if (k===0) {
 return true;
} else {
return false;
}

}

smallestCommons([1,5]);

31

My personal code for this challenge: very easy to apprehend;

function smallestCommons(arr) {
var allNum = [];
var j = 1;
// sorted array
arr = arr.sort(function(a, b){return a - b;});
var num = arr[0];
// all numbers between arr[0] and arr[1]
for (c = arr[0]; c <= arr[1]; c++) {
allNum.pushĀ©;
}
// lcm for all numbers
for (i = 1; i < allNum.length; i++) {
while (num % allNum[i] !== 0) {
j = j + 1;
num = j * allNum[0];
}
allNum[0] = num;
j = 1;
}
return num;
}

smallestCommons([1, 5]);

33

hello people. here is my solution for this challenge. its kinda basic but its clean and i think it might helpsomeone to understand the challenge. cheers

function smallestCommons(arr) {
var a=arr[0], b=arr[1] ,c;
var myArr=[];
var myFlag=[];
if (a>b){
c = a;
a = b;
b = c;
}//if
for(i=b; i>=a; iā€“){
myArr.push(i);
}//for
var smc;
var step = 1;
do {
smc = myArr[0] * myArr[1] * step;
for (i=2; i < myArr.length; i++){
if ( smc % myArr[i] === 0 ){
myFlag[i] = false;
}//if
else {
myFlag[i] = true;
}//else
}//for
step++;
}//do
while (myFlag.indexOf(true) !== -1);
return smc;
}

smallestCommons([1,5]);

34

Hello, here is my solution, also how can i improve it,

function smallestCommons(arr) {
  var largest = Math.max(arr[0],arr[1]);
  var smallest = Math.min(arr[0],arr[1]);
  var counter = 1;
  var multiple;
  var test = [false];
  
  while( test.includes(false) ){
    test = [];
    multiple = largest * counter;  
    for( var j = smallest; j < largest; j++){
      if( multiple % j == 0){
        test.push(true);
      }else{
        test.push(false);
      }
      
    }
    counter++;
  }
  return multiple;
}
smallestCommons([1,13]);
1 Like
35

This is my solution, itā€™s not perfect, but it works apparently!

function smallestCommons(arr) {
  arr = getSequentialNums(arr[0], arr[1]).reverse();
  
  return arr.reduce(function(a, b) {
    return a * b / gcd(a, b);
  });
}

// Get the numbers between the smallest number and the biggest number between a and b
function getSequentialNums(a, b) {
  var arr = [];
  for(var i = Math.min(a, b); i <= Math.max(a, b); i++) {
    arr.push(i);
  }
  
  return arr;
} 
  // returns the Greatest Common Divisor.
function gcd(a, b) {
  var remainder = a % b;

  return (remainder === 0) ? b : gcd(b, remainder);
}

smallestCommons([1,5]);
36

Tell me please, why my code doesnā€™t work?

function smallestCommons(arr) {
var max = Math.max.apply(null, arr),
min = Math.min.apply(null, arr),
result = max;

for (var i = min; i <= max; i++) {
if (result % i != 0) {
i = min;
result += max;
}
}
return result;
}
smallestCommons([14, 21]);

BUT THIS CODE WORKS

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;
}
Iā€™ve wasted much time to solve this problem and donā€™t get it

2 Likes
37

  • this uses Euclidian Algorithm - that is the gcd and lcm functions
    • gcd greatest common denominator
    • lcm least common multiple
  • you can easily follow something simple like [1,5] through the various stages of the function
    • [1,5] first becomes [1,2,3,4,5] with an if statement then a for loop then push and unshift
    • then that whole array goes into the forEach function
    • you can follow each round as the multiplier grows
1 Like
38

Additional answer --> written in java style

function smallestCommons(arr) {
  var small = arr[0];
  var large = arr[1];
  if(arr[0] > arr[1]) {
    small = arr[1];
    large = arr[0];
  }
  var fixLarge = large;
  var multiple = 0;
  while(small < fixLarge) {
    multiple = findSmallestMultiple(small, large);
    small += 1;
    large = multiple;
  }
  return multiple;
}

function findSmallestMultiple(small, large) {
  var i = 2;
  var lcm = large;
  while(lcm % small !== 0) {
    lcm = large * i;
    i++;
  }
  
  return lcm;
}
39

my solution

every function does simple thing

function smallestCommons(arr) {
  arr = complete(arr);
  return arr.reduce(function (a, b) {
    return smallestCommonMultiple(a, b);
  });
}

function complete(arr) {
  var max = Math.max(arr[0], arr[1]);
  var min = Math.min(arr[0], arr[1]);
  for (var i = min + 1; i < max; i++) {
    arr.push(i);
  }
  return arr;
}

function smallestCommonMultiple(a,b) {
  return a * b / greatestCommonDivisor(a, b);
}

function greatestCommonDivisor(a, b) {
  var num = 1;
  for (var i = 1; i <= Math.min(a,b); i++) {
    if (a % i === 0 && b % i === 0) {
      num = i;
    }
  }
  return num; 
}


smallestCommons([1,5]);
3 Likes
40

My basic solution:
thought it takes two times than the fastest one to execute, it only uses methods that are easy to understand

function smallestCommons(arr) {
  arr.sort();
  var list = [];
  var count = 0;
  var mark = [];
  var finalMultiple = 1;
  var repeatAgain = 2;
  // creat a full list from the first number to the last
  for (var x = arr[0]; x <= arr[arr.length - 1] ; x++) {
    list.push(x);
  }

  for (var i = 2; i < arr[arr.length - 1]; i++) {
    for (var num in list) {
      if (list[num] % i === 0) {
        count += 1;
        mark.push(num);
      }
    }
    //if there's more than 2 count, then we found a share number
    //that can divide the list, substitute the number with 
    if (count >= 2) {
      for (var y in mark) {
        list.splice(mark[y], 1, list[mark[y]] / i);
      }
      finalMultiple *= i;
    }
    count = 0;
    mark = [];
    
    // check again to see if there have any new smaller share number can divide the list
    repeatAgain += 1;
    if (repeatAgain == arr[arr.length - 1]) {
      i = 1;
    }
  }
  
  var partOfAnswer = list.reduce(function(multiple, value) {
    return multiple * value;
  });
  
  return finalMultiple * partOfAnswer ; 
}


smallestCommons([1, 13]);
41 
function smallestCommons(arr) {
  var max = Math.max(arr[0], arr[1]);
  var min = Math.min(arr[0], arr[1]);
  var multiple = 0;
  var multipleFound = false;
  
  while (multipleFound === false) {
    multiple += max;
    for (var i = min; i < max; i++) {
      if (multiple % i !== 0) {
        multipleFound = false;
        break;
      } else {
        multipleFound = true;
      }
    }
  }
  
  return multiple;
}
5 Likes
42 
function smallestCommons(arr) {
  //generate an array of the numbers
  var small = Math.min(arr[0], arr[1]);
  var big = Math.max(arr[0], arr[1]);
  arr[0] = small; arr[1] = big;
  var nums = [];
  for(var i = arr[0]; i <= arr[1]; i++){
    nums.push(i);
  }
  //find the Smallest Common Multiple of two numbers
  function findSCM(a,b){
    var small = a;
    var big = b;
    while(small != big){
      if(small<big){small+=a;}
      else{big+=b;}
    }
    return small;
  }
  //determine the SCM for the whole array
  var scm = 1;
  return nums.reduce(function(scm,a){
    return findSCM(scm,a);
  });
}


smallestCommons([1,5]);

The complexity of this algorithm is only 2N.
Please consider this.

2 Likes