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

JavaScript Algorithm Performance - Count the number of numbers in a range divisible by k

本文关键字：范围内 数字 性能 算法 计算 JavaScript      更新时间：2023-09-26

我创建了一个算法，用于查找范围内可被第三个数字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)

但得到了错误的答案。

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

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)

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

相关文章：