CODEWITHSUNDEEP
javascriptalgorithmmath
Ankita
Ankita

Reputation: 623

Find the multiple of n numbers within given range

How can I find the number of multiple for N numbers(as an array input) for a range 1 to K, where 1 < K < 10⁸ and 3 ≤ N < 25.

function findNumberOfMultiples(inputArray, maxSize) {   
    var count = 0;
    var tempArray = [];
    for (var i=0; i<maxSize; i++){
        tempArray[i] = 0;
    }

    for (var j=0; j<inputArray.length; j++) {
        for (var i=1; i<=maxSize; i++) {
            if (i % inputArray[j]) {
                tempArray[i-1] = 1;
            }
        }
    }

    for (var i=0; i<maxSize; i++) {
        if (tempArray[i]==1) {
            count++;
        }
    }
 return count;
}

The above program fails for large number K. For example, if inputArray = [2,3,4] and maxSize(k) is 5,

so total number of mutiple of 2 or 3 or 4 is 3 in range 1 to 5

Upvotes: 0

Views: 921

Answers (2)

Karthik
Karthik

Reputation: 5040

You can solve this in O(N^2) where N is the number of elements in your array.

let us say you have two element in your array [a1,a2] and the range is K

your answer will be = > 

  K/a1 + K/a2 - K/lcm(a1,a2) // because you added them in both a1 and a2

So If you have a1,.....ax elements, your answer would be

K/a1+.....K/ax - K/lcm(ai,aj) (you have to replace i,j by (n*n-1)/2 combinations.

You will have to do K/lcm(ai,aj) O(N^2) times ((n*n-1)/2 time to be precise). So the algorithm complexity will be O(N^2) (There will be a Log(min(ai,aj)) factor but that would not make much difference to the overall complexity). This will work any K as it only depends on your innput array size.

 public int combinations(int K, int[] input){
    int total = 0;
    for(int i=0;i<input.length;i++){
        total  =  total + Math.floor(K/input[i]);
    }
    for(int i=0;i<input.length;i++){
        for(int j=i+1;j<input.length;j++){
            if(i!=j){
                int lcm =lcmFind(input[i], input[j]);
                total = total - Math.floor(K/lcm);
            }
        }
    }
    return total;
}

The test case you have provided:

enter image description here

Upvotes: 2

Pierre Maoui
Pierre Maoui

Reputation: 6384

This function seems to do the trick : 

var findMultiplesLength = function(arrayInput, max) {
  var globalMultiples = [];
  for (var j = 0; j < arrayInput.length; j++) {
    var x = arrayInput[j];
    var n = max / x;
    for (var i=1; i < n; i++) {
      mult = i * x;
      if (globalMultiples.indexOf(mult) === -1) {
        globalMultiples.push(mult);
      }
    }
  }
  return globalMultiples.length;
};

EDIT : You won't have any stack error but choosing big values for the range may hang your browser.

Upvotes: 1

Related Questions