javascript - 求给定范围内 n 个数的倍数

Question

如何找到 1 到 K 范围内 N 个数字(作为数组输入)的倍数，其中 1 < K < 10⁸ 和 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;
}

上面的程序对于大数 K 失败。例如，如果 inputArray = [2,3,4] 和 maxSize(k) 是 5，

• 2 的倍数是 2,4
• 3的倍数是3
• 4的倍数是4

所以 2 或 3 或 4 的倍数总数是 3 在范围 1 到 5

Answer 1

您可以在 O(N^2) 中解决此问题，其中 N 是数组中元素的数量。

假设你的数组 [a1,a2] 中有两个元素，范围是 K

你的答案将是 = >

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

所以如果你有 a1,.....ax 元素，你的答案就是

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

您将不得不执行 K/lcm(ai,aj) O(N^2) 次(准确地说是 (n*n-1)/2 次)。所以算法复杂度将是 O(N^2) (会有一个 Log(min(ai,aj)) 因子，但这不会对整体复杂度产生太大影响)。这将适用于任何 K，因为它仅取决于您的 innput 数组大小。

 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;
}

您提供的测试用例: