CountDiv (Codility) 挑战算法的性能问题

Question

需要一些关于我为解决这个 codility 挑战而制定的算法的帮助：

\n\n

编写一个函数，给定三个整数 A、B 和 K，返回 [A..B] 范围内可被 K 整除的整数个数。\n例如，对于 A = 6、B = 11 和 K = 2 ，你的函数应该返回 3，因为在 [6..11] 范围内有 3 个数字可以被 2 整除，即 6、8 和 10。
\nA 和 B 是 [0..2,000,000,000] 范围内的整数；\nK是 [1..2,000,000,000] 范围内的整数；\nA \xe2\x89\xa4 B.

\n\n

public class Solution {\n        public int solution(int A, int B, int K) {\n\n            int counter = 0;\n            ArrayList<Integer> listOfNumbersInBetween = new ArrayList<>();\n\n            for (int i = A; i <= B; i++) {\n                listOfNumbersInBetween.add(i);\n            }\n\n            for (int arrayElement : listOfNumbersInBetween) {\n                if (arrayElement % K == 0) {\n                    counter++;\n                }\n            }\n\n            return counter;\n\n        }}\n

\n\n

正如您所看到的，我的解决方案工作完美，但由于时间复杂度 O(BA)，其性能得分为 0%。

\n\n

我怎样才能改进这段代码以使其得分 100%？

\n

Answer 1

使用循环是蛮力，而像这样的挑战不能用蛮力来完成。

这意味着您必须计算结果。像这样的挑战更多的是数学问题而不是编程问题，所以戴上数学帽子吧。

所以想一想。在一个整数范围内，计算有多少个整数可以被 K 整除。如果我让你手动执行此操作（允许使用简单的计算器），而不使用计算机暴力破解，你会怎么做？111例如，找出和之间有多少个整数999可以被整除13

暗示

找到可被 K 整除的范围中的第一个数字，以及可被 K 整除的范围中的最后一个数字。对于上面的示例，这将是117和988。

现在计算从第一个整数到最后一个整数有多少个整数可以被 K 整除，记住对它们都进行计数。117那么，和之间有多少个整数988可以被 整除13？

答案：(988 - 117) / 13 + 1 = 871 / 13 + 1 = 67 + 1 = 68