JavaScript算法性能 - 计算可被k整除的范围内的数字数

Question

我创建了一个算法,用于查找范围内可被第三个数字k整除的数字.我得到了这个工作,但在多项式时间而不是线性时间

function divisibleCount(x, y, k) {
    var count = 0;
    for (var i = x; i <= y; i++) {
        if (i % k === 0) {
            count++;
        }
    return count;
}

论点如下

x: Start of range
y: End of range
K: Number is divisible by

问题肯定是for循环,这使得这个多项式时间.

我试图用

for (var i = x; i <= k; i += k)

但得到了错误的答案.

有什么方法可以改善这个吗？

Answer 1

O(1).

像这样的东西:

Math.floor((y-1) / k) - Math.floor((x-1) / k)

说明:

Math.floor((x-1)/ k)是在间隔之前可被k整除的数字的数量.

Math.floor((y-1)/ k)是可以被k整除的数字,直到间隔结束.

应该是正数,k> 0.希望;)

编辑:我明白了,你想在范围中包含y.好的,然后改为:

Math.floor(y / k) - Math.floor((x-1) / k)

这是作业吗？我感到有点内疚.