CODEWITHSUNDEEP
javascriptarrays
Liad Livnat
Liad Livnat

Reputation: 7475

Find the lowest common divisor in divisors array

i have a math question in javascript:

I have array of divisors :

var divisors = ["3","4","5","10","12","15","20","30","60"]

and number of items that should be divide without a reminder in one of those items:

var items_to_divide = ["10","30"]

i'm looking for a function that will give me the lowest common divisors from list of divisors (var divisors) between in items_to_divide.

In this example the result should be 5, cause 10 / 5 = 2 and 30 / 5 = 6 so 5 is the lowest common divider, cause they both divide with 5 without a reminder.

anyone can suggest a nice logic here?

Upvotes: 1

Views: 1653

Answers (3)

Samuel Caillerie
Samuel Caillerie

Reputation: 8275

I suggest the following steps :

  1. Sort your divisor array ascending
  2. Loop on this array
  3. Check if the current divisor divides all items to divide
  4. if yes, this is the lowest common divider.

An implementation of this algorithm could be this one :

function best_divisor() {
  var division;

  // Sort divisor array from lowest value to highest one
  divisors = divisors.sort(function(a,b) {return +a > +b;});

  // Test each value of this array
  for (var i=0; i<divisors.length; i++) {
    divide = true;

    // check if it divides all values from the items_to_divide
    for (var j=0; j<items_to_divide.length; j++) {
      division = items_to_divide[j] / divisors[i];
      if(division !== Math.round(division)) {
        divide = false;
        break;
      }
    }

    // If all divisions give integers, this divisor is the lowest one
    if(divide) return divisors[i];
  }

  // No divisor found
  return -1;
}

Upvotes: 2

Rickard Staaf
Rickard Staaf

Reputation: 2740

This will make sure it does not continue to search for divisors once it has found the lowest.

var divisors = [3, 4, 5, 10, 12, 15, 20, 30, 60];
var items_to_divide = [10, 30];
var divisor = false;
for (var i = 0; i < divisors.length; i++) {
    var divisorfound = true;
    for (var j = 0; j < items_to_divide.length; j++) {
        if (items_to_divide[j] % divisors[i] !== 0) {
            divisorfound = false;
            break;
        }
    }
    if (divisorfound === true) {
        divisor = divisors[i];
        break;
    }
}
console.log(divisor);

Upvotes: 1

Alfred Huang
Alfred Huang

Reputation: 18235

var answer = NaN;
for(var i = 0; i < divisors.length; ++i) {
    var ok = true;
    for(var j = 0; j < items_to_divide.length; ++j) {
        if(parseInt(items_to_divide) % parseInt(divisors[i]) != 0) {
            ok = false;
            break;
        }
    }
    answer = answer && Math.min(ans || parseInt(divisors[i]), parseInt(divisors[i]));
}

console.log(answer);

Upvotes: 1

Related Questions