Smallest Common Multiple - Infinite Loop

Question

I'm working on a freeCodeCamp exercise called Smallest Common Multiplier. The purpose of the exercise is the following:

Find the smallest common multiple of the provided parameters that can be evenly divided by both, as well as by all sequential numbers in the range between these parameters.

The range will be an array of two numbers that will not necessarily be in numerical order.

e.g. for 1 and 3 - find the smallest common multiple of both 1 and 3 that is evenly divisible by all numbers between 1 and 3.

I thought I could save this by sorting the elements in the array passed to the function from smallest to largest, then check with a for loop for all the numbers whether or not number % x === 0. I then though to encapsulate everything in a while loop that check the number of dividers (if the number of dividers is smaller that the highest number I'm checking for, repeat the process.

It seems that I've written an infinite loop that crashes my browser.

function smallestCommons(arr) {

  //sort from smallest to largest
  arr.sort(function(a, b) {
    return a-b;
  });

  var result = 1;
  var divisors = [];

  //while number of divisors !== last number to check
  while(divisors.length < arr[1]) {
    //check if number divides result
    for(var x = arr[0]; x < arr[1]; x++) {
      //if it divides result
      if(result % x === 0) {
        //push it to divisors
        divisors.push(x);
      }
      else {
        //clear divisors
        divisors = [];
      }
    }
    //check next number
    result++;
  }

  return result;
}


smallestCommons([5,1]);

Can you point out what I'm doing wrong, and maybe point out how to approach the exercise?

Answer 1

Here's another solution to this problem. The code is easy to understand thanks to the comments.

/**
 * Find the smallest common multiple of the provided integers
 * that can be evenly divided by both, as well as by all sequential numbers in
 * the range between these integers.
 *
 * @param arr Array containing two integers.
 * @returns The smallest common multiple.
 */
function smallestCommons(arr) {
  let min = Math.min(arr[0], arr[1]);
  let max = Math.max(arr[0], arr[1]);
  let i = 1;
  while (!divisibleByAll(min, max, max * i)) {
    i++;
  }
  return max * i;
}

/**
 * This function checks whether c is divisible by a and b.
 *
 * @param a An integer lower than b.
 * @param b An integer greater than a.
 * @param c An integer, to check if it is divisible by a and b.
 * @returns True c is divisible by a and b, false otherwise.
 */
function divisibleByAll(a, b, c) {
  for (let i = a; i <= b; i++) {
    if (c % i != 0) {
      return false;
    }
  }
  return true;
}

console.log(smallestCommons([1, 5])); // 60
console.log(smallestCommons([2, 10])); // 2520
console.log(smallestCommons([1, 13])); // 360360

Answer 2

// noprotect
    function smallestCommons(arr) {
        var value = Math.max.apply(null, arr) * Math.min.apply(null, arr) - 1;
        var succ = false;
        do {
            value++;
            for (var i = Math.min.apply(null, arr); i <= Math.max.apply(null, arr); i++) {
                if (value % i != 0) {
                    succ = false;
                    break;

                }
                succ = true;

            }
        } while (!succ);

        return value;
    }

Answer 3

Since you asked how to approach the exercise:

Recall that the least common multiple is equal to:

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

(See: Wikipedia). The greatest common divisor function, gcd, can be implemented using the Euclidean algorithm:

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

Now that lcm is implemented, and using the fact that, mathematically, lcm(a, b, c) === lcm((lcm(a, b), c), we just need a way to generate a range of numbers comprising the given start and end and then reduce that range to their least common multiple, like this:

function range(start, end) {
  return [...Array(end - start + 1)].map((_, i) => start + i);
}

function smallestCommons(arr) {
  const start = Math.min(...arr);
  const end = Math.max(...arr);

  return range(start, end).reduce(function(a, b) {
    return lcm(a, b);
  });
}

And that's a wrap:

> smallestCommons([1, 5])
> 60
> smallestCommons([5, 1])
> 60
> smallestCommons([1, 13])
> 360360
> smallestCommons([23, 18])
> 6056820

Answer 4

As many seem to be struggling with this challenge (I struggled with others...), maybe you guys find my solution helpful. It's pretty straightforward, actually:

// noprotect
function smallestCommons(arr) {

  arr = arr.sort();
  var multiple = 0;


  function test(num) {
    for (var j = arr[0]; j<=arr[1]; j++) {
      if (num % j !== 0) return false;
    }
  return true;
  }


  for (var i = arr[1]*2; i<100000000; i++) {
    if (test(i)){
       multiple = i;
       break;
    }
  }

  return multiple;
}

The 'test' function tests whether a given number ('num') is a common multiple of the parameters provided and all the numbers in between. The for loop loops through all positive numbers until one number meets this test, returning this number as our solution. We can skip some numbers, starting with the greatest parameter times two (arr[1]*2), because the least common multiple cannot possibly be smaller than this (right?). But one might as well just start with i=1. Hope this helps!

Answer 5

You can use following function for Smallest common Multiplier. However, it will run in a very big loop for bigger inputs and differences.

So it will depend on the environment you are running your code in. If you try this code in https://jsfiddle.net/qf4snysL/ you will get correct output. But in FCC it may give infinite loop for input [18, 23].

function smallestCommons(arr) {
var range = arr.sort();
  //alert(range);
  var array = [];
  for(var i=arr[0];i<=arr[arr.length-1];i++){
  array.push(i);
  }
var x=true;
var LCM=0;
while(x){
  LCM++;
  for(var j = array[0]; j <=array[array.length-1];j++){
    if(LCM % j !==0){
      break;
    }
    else if(j==array[array.length-1]){
    x=false;
    }
  }
}
return LCM;

}
smallestCommons([18,23]);

//noprotect

Look at the //noprotect at the bottom, it is there for special purpose.

Answer 6

Here's my javascript solution, perhaps you will find it useful reference:

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 7

Notice that you clean divisors array in the else part of your function. That way you can't pass the condition divisors.length >= arr[1]

However your implementation of LCM is not working at all