How to find the least common multiple of a range of numbers?

Question

Given an array of two numbers, let them define the start and end of a range of numbers. For example, [2,6] means the range 2,3,4,5,6. I want to write javascript code to find the least common multiple for the range. My code below works for small ranges only, not something like [1,13] (which is the range 1,2,3,4,5,6,7,8,9,10,11,12,13), which causes a stack overflow. How can I efficiently find the least common multiple of a range?

function leastCommonMultiple(arr) {
    var minn, max;
    if ( arr[0] > arr[1] ) {
        minn = arr[1];
        max = arr[0];
    } else {
        minn = arr[0];
        max = arr[1];
    }
    function repeatRecurse(min, max, scm) {
        if ( scm % min === 0 && min < max ) {
            return repeatRecurse(min+1, max, scm);
        } else if ( scm % min !== 0 && min < max ) {
            return repeatRecurse(minn, max, scm+max);
        }
        return scm;
    } 
    return repeatRecurse(minn, max, max);
}

Answer 1

I think this gets the job done.

function leastCommonMultiple(min, max) {
    function range(min, max) {
        var arr = [];
        for (var i = min; i <= max; i++) {
            arr.push(i);
        }
        return arr;
    }

    function gcd(a, b) {
        return !b ? a : gcd(b, a % b);
    }

    function lcm(a, b) {
        return (a * b) / gcd(a, b);   
    }

    var multiple = min;
    range(min, max).forEach(function(n) {
        multiple = lcm(multiple, n);
    });

    return multiple;
}

leastCommonMultiple(1, 13); // => 360360

Answer 2

function smallestCommons(arr) {
  var max = Math.max(...arr);
  var min = Math.min(...arr);
  var candidate = max;

  var smallestCommon = function(low, high) {
    // inner function to use 'high' variable
    function scm(l, h) {
      if (h % l === 0) {
        return h;
      } else {
        return scm(l, h + high);
      }
    }
    return scm(low, high);
  };

  for (var i = min; i <= max; i += 1) {
    candidate = smallestCommon(i, candidate);
  }

  return candidate;
}

smallestCommons([5, 1]); // should return 60
smallestCommons([1, 13]); // should return 360360
smallestCommons([23, 18]); //should return 6056820

Answer 3

As this question has recently been revived, here's what I think is a simpler take on the question, writing very simple helper functions to calculate the greatest common divisor of two integers (gcd), to calculate the least common multiple of two integers (lcm), to calculate the least common multiple of an array of integers (lcmAll), to generate the range of integers between two given integers (rng), and finally, in our main function, to calculate the least common multiple of the range of integers between two given integers (lcmRng):

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 (hi - lo + 1)] .map ((_, i) => lo + i)

const lcmRng = (lo, hi) => lcmAll (rng (lo, hi))

console .log (lcmRng (1, 13))

All of these functions are simple. Although the question was tagged recursion, only gcdis recursive. If this is an attempt to play with recursion, we could rewrite lcmAll in a recursive manner with something like this:

const lcmAll = (ns) => 
  ns.length == 0 
    ? 1 
    : lcm(ns[0], lcmAll(ns .slice (1)))

Although I'm a big fan of recursion, I see no other reason to choose the recursive version here over the reduce one. In this case, reduce is cleaner.

And finally, if you really want the API originally requested where the range bounds are passed in an array, you could write one more wrapper:

const leastCommonMultiple = ([lo, hi]) => lcmRng (lo, hi)

leastCommonMultiple ([1, 13]) //=> 360360

Answer 4

LCM function for a range [a, b]

// Euclid algorithm for Greates Common Divisor
function gcd(a, b)
{ 
 return !b ? a : gcd(b, a % b);
} 

// Least Common Multiple function
function lcm(a, b) 
{
 return a * (b / gcd(a,b));
}

// LCM of all numbers in the range of arr=[a, b] 
function range_lcm(arr)
{
 // Swap [big, small] to [small, big]
 if(arr[0] > arr[1]) (arr = [arr[1], arr[0]]);

 for(x = result = arr[0]; x <= arr[1]; x++) {
  result = lcm(x, result);
 }
 
 return result; 
}

alert(range_lcm([8, 5])); // Returns 840

Answer 5

I found the other answers to be somewhat confusing while I was figuring out the best way to do this with just two numbers, so I looked found the most optimal solution on Wikipedia.

https://en.wikipedia.org/wiki/Least_common_multiple#Calculation

The most efficient way to find the least common multiple of two numbers is (a * b) / greatestCommonDivisor(a, b);

To do this we need to calculate the greatest common denominator. The most efficient way to do that is using Euclid's algorithm.

https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm

Here is the complete solution for two numbers in case anyone else lands on this question but only needs to calculate for two numbers:

const leastCommonMultiple = (a, b) => (a * b) / greatestCommonDivisor(a, b);

const greatestCommonDivisor = (a, b) => {
  const remainder = a % b;
  if (remainder === 0) return b;
  return greatestCommonDivisor(b, remainder);
};

Answer 6

Mine is not as fancy as the other answers but I think it is easy to read.

function smallestCommons(arr) {
 //order our array so we know which number is smallest and which is largest
 var sortedArr = arr.sort(sortNumber),
 //the smallest common multiple that leaves no remainder when divided by all the numbers in the rang
 smallestCommon = 0,
 //smallest multiple will always be the largest number * 1;
 multiple = sortedArr[1];

 while(smallestCommon === 0) {
  //check all numbers in our range
  for(var i = sortedArr[0]; i <= sortedArr[1]; i++ ){
   if(multiple % i !== 0 ){
    //if we find even one value between our set that is not perfectly divisible, we can skip to the next multiple
    break;
   }

   //if we make it all the way to the last value (sortedArr[1]) then we know that this multiple was perfectly divisible into all values in the range
   if(i == sortedArr[1]){
    smallestCommon = multiple;
   }

  }

  //move to the next multiple, we can just add the highest number.
  multiple += sortedArr[1];
 }

 console.log(smallestCommon);
 return smallestCommon;
}

function sortNumber(a, b) {
    return a - b;
}


smallestCommons([1, 5]); // should return 60.
smallestCommons([5, 1]); // should return 60.
smallestCommons([1, 13]); // should return 360360.
smallestCommons([23, 18]); // should return 6056820.

Edit: Turned answer into snippet.

Answer 7

This is a non-recursive version of your original approach.

function smallestCommons(arr) {
  // Sort the array
  arr = arr.sort(function (a, b) {return a - b}); // numeric comparison;
  var min = arr[0];
  var max = arr[1];

  var numbers = [];
  var count = 0;

  //Here push the range of values into an array
  for (var i = min; i <= max; i++) {
    numbers.push(i);
  }
  //Here freeze a multiple candidate starting from the biggest array value - call it j
  for (var j = max; j <= 1000000; j+=max) {

    //I increase the denominator from min to max
    for (var k = arr[0]; k <= arr[1]; k++) {

      if (j % k === 0) { // every time the modulus is 0 increase a counting 
        count++; // variable
      }
    }

    //If the counting variable equals the lenght of the range, this candidate is the least common value
    if (count === numbers.length) { 
      return j; 
    }
    else{
      count = 0; // set count to 0 in order to test another candidate
    }
  }
}

alert(smallestCommons([1, 5]));

Answer 8

Hey I came across this page and wanted to share my solution :)

function smallestCommons(arr) {
  var max = Math.max(arr[0], arr[1]),
      min = Math.min(arr[0], arr[1]),
      i = 1;
  while (true) {
    var count = 0;
    for (j = min; j < max; j++) {
      if (max * i % j !== 0) {
        break;
      }
      count++;
    }
    if (count === (max - min)) {
      alert(max * i);
      return max * i;
    }
    i++;
  }
}
smallestCommons([23, 18]);

Answer 9

 function leastCommonMultiple(arr) {
    /*
      function range(min, max) {
        var arr = [];
       for (var i = min; i <= max; i++) {
        arr.push(i);
      }
       return arr;
    }
    */
    var min, range;
     range = arr;
    if(arr[0] > arr[1]){
       min = arr[1];
    }
    else{
       min = arr[0]
    }

    function gcd(a, b) {
        return !b ? a : gcd(b, a % b);
    }

    function lcm(a, b) {
        return (a * b) / gcd(a, b);   
    }

   var multiple = min;
    range.forEach(function(n) {
       multiple = lcm(multiple, n);
    });

   return multiple;
}

console.log( leastCommonMultiple([1, 13]) )

Answer 10

Well played on the solution. I think I got one that might be abit shorter just for future reference but ill definatly look into yours

function LCM(arrayRange) {
    var newArr = [];

    for (var j = arrayRange[0]; j <= arrayRange[1]; j++){
        newArr.push(j);
    }

    var a = Math.abs(newArr[0]);
    for (var i = 1; i < newArr.length; i++) {
        var b = Math.abs(newArr[i]),
            c = a;

        while (a && b) {
            a > b ? a %= b : b %= a;
        }
        a = Math.abs(c * newArr[i] / (a + b))
    }
   return console.log(a);
}

LCM([1,5]);

Answer 11

You may have originally had a stack overflow because of a typo: you switched between min and minn in the middle of repeatRecurse (you would have caught that if repeatRecurse hadn’t been defined in the outer function). With that fixed, repeatRecurse(1,13,13) returns 156.

The obvious answer to avoiding a stack overflow is to turn a recursive function into a non-recursive function. You can accomplish that by doing:

function repeatRecurse(min, max, scm) {
    while ( min < max ) {
        while ( scm % min !== 0 ) {
            scm += max;
        }
        min++;
    }
}

But perhaps you can see the mistake at this point: you’re not ensuring that scm is still divisible by the elements that came before min. For example, repeatRecurse(3,5,5)=repeatRecurse(4,5,15)=20. Instead of adding max, you want to replace scm with its least common multiple with min. You can use rgbchris’s gcd (for integers, !b is the same thing as b===0). If you want to keep the tail optimization (although I don’t think any javascript engine has tail optimization), you’d end up with:

function repeatRecurse(min, max, scm) {
    if ( min < max ) {
        return repeatRecurse(min+1, max, lcm(scm,min));
    }
    return scm;
} 

Or without the recursion:

function repeatRecurse(min,max,scm) {
    while ( min < max ) {
        scm = lcm(scm,min);
        min++;
    }
    return scm;
}

This is essentially equivalent to rgbchris’s solution. A more elegant method may be divide and conquer:

function repeatRecurse(min,max) {
    if ( min === max ) {
        return min;
    }
    var middle = Math.floor((min+max)/2);
    return lcm(repeatRecurse(min,middle),repeatRecurse(middle+1,max));
}

I would recommend moving away from the original argument being an array of two numbers. For one thing, it ends up causing you to talk about two different arrays: [min,max] and the range array. For another thing, it would be very easy to pass a longer array and never realize you’ve done something wrong. It’s also requiring several lines of code to determine the min and max, when those should have been determined by the caller.

Finally, if you’ll be working with truly large numbers, it may be better to find the least common multiple using the prime factorization of the numbers.

Answer 12

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

function gcd (x, y) {
  return (x % y === 0) ? y : gcd(y, x%y);
}

function lcm (x, y) {
  return (x * y) / gcd(x, y); 
}

function lcmForArr (min, max) {
  var arr = range(min, max);
  return arr.reduce(function(x, y) {
    return lcm(x, y); 
  });
}

range(10, 15); // [10, 11, 12, 13, 14, 15]
gcd(10, 15); // 5
lcm(10, 15); // 30
lcmForArr(10, 15); //60060

Answer 13

How about:

// Euclid Algorithm for the Greatest Common Denominator
function gcd(a, b) {
    return !b ? a : gcd(b, a % b);
  }
  // Euclid Algorithm for the Least Common Multiple

function lcm(a, b) {
    return a * (b / gcd(a, b));
  }
  // LCM of all numbers in the range of arr = [a, b];

function smallestCommons(arr) {
  var i, result;
  // large to small - small to large
  if (arr[0] > arr[1]) {
    arr.reverse();
  } // only happens once. Means that the order of the arr reversed.
  for (i = result = arr[0]; i <= arr[1]; i++) { // all numbers up to arr[1] are arr[0].
    result = lcm(i, result); // lcm() makes arr int an integer because of the arithmetic operator.
  }
  return result;
}
smallestCommons([5, 1]); // returns 60

Answer 14

function lcm(arr) {
  var max = Math.max(arr[0],arr[1]),
      min = Math.min(arr[0],arr[1]),
      lcm = max;
  var calcLcm = function(a,b){
    var mult=1;
    for(var j=1; j<=a; j++){
      mult=b*j;
      if(mult%a === 0){
        return mult;
      }
    }
  };
  for(var i=max-1;i>=min;i--){
    lcm=calcLcm(i,lcm);
  }
  return lcm;
}
lcm([1,13]); //should return 360360.

Answer 15

    /*Function to calculate sequential numbers 
in the range between the arg values, both inclusive.*/
    function smallestCommons(arg1, arg2) {
     
       if(arg1>arg2) { // Swap arg1 and arg2 if arg1 is greater than arg2
          var temp = arg1;
          arg1 = arg2;
          arg2 =temp;
        }
      
      /*
      Helper function to calculate greatest common divisor (gcd)
      implementing Euclidean algorithm */
      function gcd(a, b) {
       return b===0 ? a : gcd(b, a % b); 
       }
      
      /*
      Helper function to calculate lowest common multiple (lcm) 
of any two numbers using gcd function above */
       function lcm(a,b){
          return (a*b)/gcd(a,b);
         }
      
      var total = arg1; // copy min value
      for(var i=arg1;i<arg2;i++){
          total = lcm(total,i+1);
         }
      //return that total
      return total;
    }
    /*Yes, there are many solutions that can get the job done.
    Check this out, same approach but different view point.
    */
    console.log(smallestCommons(13,1)); //360360

Answer 16

Here's my solution. I hope you will find it easy to follow:

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

  var smallestCommon = min * max;

  var doneCalc = 0;

  while (doneCalc === 0) {
    for (var i = min; i <= max; i++) {
      if (smallestCommon % i !== 0) {
        smallestCommon += max;
        doneCalc = 0;
        break;
      }
      else {
        doneCalc = 1;
      }
    }
  }

  return smallestCommon;
}

Answer 17

Here is another nonrecursive for-loop solution

function smallestCommons(arr) {
  var biggestNum = arr[0];
  var smallestNum = arr[1];
  var thirdNum;
  //make sure biggestNum is always the largest
  if (biggestNum < smallestNum) {
    thirdNum = biggestNum;
    biggestNum = smallestNum;
    smallestNum = thirdNum;
  }
  var arrNum = [];
  var count = 0;
  var y = biggestNum;

  // making array with all the numbers fom smallest to biggest
  for (var i = smallestNum; i <= biggestNum; i += 1) {
    arrNum.push(i);
  }

  for (var z = 0; z <= arrNum.length; z += 1) {
    //noprotect
    for (y; y < 10000000; y += 1) {
      if (y % arrNum[z] === 0) {
        count += 1;
        break;
      }
      else if (count === arrNum.length) {
        console.log(y);
        return y;
      }
      else {
        count = 0;
        z = 0;
      }
    }
  }
}
smallestCommons([23, 18]);

Answer 18

function smallestCommons(arr) {
  var sortedArr = arr.sort(); // sort array first
  var tempArr = []; // create an empty array to store the array range
  var a = sortedArr[0];
  var b = sortedArr[1];
  for(var i = a; i <= b; i++){
    tempArr.push(i);
  }
  // find the lcm of 2 nums using the Euclid's algorithm
  function gcd(a, b){
    while (b){
      var temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

  function lcm(a, b){
    return Math.abs((a * b) / gcd(a, b));
  }
  var lcmRange = tempArr.reduce(lcm);


  return lcmRange;
}

Answer 19

function smallestCommons(arr) {
    let smallest, biggest, min;
    arr.reduce(function (a, b) {
        biggest = Math.max(a, b);
    });
    const max = biggest;
    arr.reduce(function (a, b) {
        smallest = Math.min(a, b);
        min = smallest;
    });
    check: while (true) {
        biggest += max;
        for (min = smallest; min < max; min++) {
            if (biggest % min != 0) {
                continue check;
            }
            if (min == (max - 1) && biggest % min == 0) {
                console.warn('found one');
                return biggest;
            }
        }
    }
}

Answer 20

    function smallestCommons(arr) {
      let min = Math.min(arr[0], arr[1]);
      let max = Math.max(arr[0], arr[1]);
      let scm = max;

      //calc lcm of two numbers:a,b;
      const calcLcm = function(a, b) {
        let minValue = Math.min(a, b);
        let maxValue = Math.max(a, b);
        let lcm = maxValue;
        while (lcm % minValue !== 0) {
          lcm += maxValue;
        }
        return lcm;
      }

      //calc scm in range of arr;
      for (let i = max; i >= min; i--) {
        scm = calcLcm(scm, i);
      }
      console.log(scm);
      return scm;
    }

    smallestCommons([1, 13]);

Answer 21

this is another very simple way and have low complexity.

function smallestCommons(arr) {
  let smallestNum = arr[0] < arr[1] ? arr[0] : arr[1];
  let greatestNum = arr[0] > arr[1] ? arr[0] : arr[1];
  let initalsArr = [];
  for(let i = smallestNum; i <= greatestNum; i++){
    initalsArr.push(i);
  }
  let notFoundFlag = true;
  let gNMltpl = 0;
  let filteredArrLen; 
  while(notFoundFlag){
    gNMltpl += greatestNum;
    filteredArrLen = initalsArr.filter((num)=>{
      return (gNMltpl / num) === Math.floor((gNMltpl / num)) 
    }).length;
    if(initalsArr.length == filteredArrLen){
      notFoundFlag = false;
    }
  }
  return gNMltpl;
}

Answer 22

My solution using es6 feature is

Lcm of given numbers

  const gcd = (a, b) => (!b ? a : gcd(b, a % b));

  const lcm = (a, b) => a * (b / gcd(a, b));

  const getLcm = (arr) => {

    const numbers = arr.sort((a, b) => parseInt(a) - parseInt(b));

    let result = parseInt(numbers[0]);

    for (let i = 1; i < numbers.length; i++) {
      result = lcm(parseInt(result), parseInt(numbers[i + 1]));
    }

    return result;
  };

Hcf of given numbers

  const getHcf = (arr) => {

    const numbers = arr.sort((a, b) => parseInt(a) - parseInt(b));

    let result = parseInt(numbers[0]);

    for (let i = 1; i < numbers.length; i++) {
      result = gcd(parseInt(numbers[i]), parseInt(result));
    }

    return result;
  };

Call like this

  console.log(getLcm([20, 15, 10, 40])). Answer 120

  console.log(getHcf([2, 4, 6, 8, 16])). Answer 2

Answer 23

I also found myself working on this challenge on my freeCodeCamp JavaScript Certification. This is what I have been able to come up with:

function smallestCommons(arr) {

    let newArr = [];
  
    // create a new array from arr [min, min + 1,......., max - 1, max]
    for (let i = Math.min(...arr); i <= Math.max(...arr); i++){
      newArr.push(i);
    }
  
    // let the max of newArr be the smallestCommonMultiple initially
    let largest = Math.max(...newArr);
    let smallestCommonMultiple = largest;
    
    // If the supposedly smallestCommonMultiple fail on any of elements in 
    //newArr add the max element until we find the smallestCommonMultiple. 
    while (newArr.some(element => smallestCommonMultiple % element !== 0)){
      smallestCommonMultiple += largest; 
    }
  
    return smallestCommonMultiple; 
 }
 
 console.log(smallestCommons([23, 18]));

Answer 24

i think it will work.

 var a = [2, 6];
    
    function getTotalX(a) {
      var num = 1e15;
      var i; 
      var arr = [];
      for (i = 1; i <=num ; i++){
        arr.push(i);
      }
     
      for (i = 0; i < a.length; i++){
        var filterArr = arr.filter((val, ind, arr) => (val % a[i] === 0));
      }
      
     console.log(filterArr[0]); // will return 6
      
    }

Answer 25

I've made a similar function in typescript that does the same task but only without recursion...

function findLowestCommonMultipleBetween(start: number, end: number): number {
  let numbers: number[] = [];

  for (let i = start; i <= end; i++) {
    numbers.push(i);
  }

  for (let i = 1; true; i++) {
    let divisor = end * i;

    if (numbers.every((number) => divisor % number == 0)) {
      return divisor;
    }
  }
}

Answer 26

function smallestCommons(arr) {
    let min = Math.min(...arr);
    let max = Math.max(...arr);
    let rangArr = [];
    for(let i = min; i <= max; i++) rangArr.push(i);
    let smallestCommon = max;
    while(!rangArr.every(e => smallestCommon % e === 0)){
        smallestCommon += max;
    }
    return smallestCommon;
}


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

Answer 27

function smallestCommons(arr) {
    arr = arr.sort((a, b) => a - b)
    let range = []
    for (let i = arr[0]; i <= arr[1]; i++) {
        range.push(i)
    }

    for(let i = arr[1]; ; i++){
        if(range.every((num => i % num == 0))){
            return i
        }
    }
}

Answer 28

function smallestCommons(arr) {
  // Kind of a brute force method, It's not fancy but it's very simple and easy to read :P

  // make an array with all the numbers in the range.
  let numbersArr = [];
  for (let i = Math.min(...arr); i <= Math.max(...arr); i++) {
    numbersArr.push(i);
  }

  // keep multiplying the biggest number until it's divisible by all the numbers in the numbersArr array.
  let scm = Math.max(...arr);
  while (true) {
    if (numbersArr.every(num => scm % num === 0)) {
      return scm;
    } else {
      scm += Math.max(...arr);
    }
  }
}

smallestCommons([2, 10]); // returns 2520.
smallestCommons([1, 13]); // returns 360360.
smallestCommons([23, 18]); // returns 6056820.

Answer 29

function leastCommonMultiple(arr) {
  // Setup
  const [min, max] = arr.sort((a, b) => a - b);
  // Largest possible value for LCM
  let upperBound = 1;
  for (let i = min; i <= max; i++) {
    upperBound *= i;
  }
  // Test all multiples of 'max'
  for (let multiple = max; multiple <= upperBound; multiple += max) {
    // Check if every value in range divides 'multiple'
    let divisorCount = 0;
    for (let i = min; i <= max; i++) {
      // Count divisors
      if (multiple % i === 0) {
        divisorCount += 1;
      }
    }
    if (divisorCount === max - min + 1) {
      return multiple;
    }
  }
}

//for a test
leastCommonMultiple([1, 5]);

Answer 30

function findSmallestCommonMultipleOfRangeOfNumbers(arr) {
let sortedArr = arr.concat([]).sort((a,b)=> a-b)
let min = sortedArr[0]
let max = sortedArr[1]
function range(min, max) {
const myRangeArr = [];
for (let i = min; i <= max; i++) {
myRangeArr.push(i);
}
return myRangeArr;
}

function gcd(a, b) {
return !b ? a : gcd(b, a % b);
}

function lcm(a, b) {
return (a * b) / gcd(a, b); 
}

let smallestCommonMultiple = min;
range(min, max).forEach(function(n) {
smallestCommonMultiple = lcm(smallestCommonMultiple, n);
});

return smallestCommonMultiple;
}

console.log(findSmallestCommonMultipleOfRangeOfNumbers([23,18]));