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

Question

我需要一些帮助来解决这个 codility 挑战的算法:

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

public class Solution {
        public int solution(int A, int B, int K) {

            int counter = 0;
            ArrayList<Integer> listOfNumbersInBetween = new ArrayList<>();

            for (int i = A; i <= B; i++) {
                listOfNumbersInBetween.add(i);
            }

            for (int arrayElement : listOfNumbersInBetween) {
                if (arrayElement % K == 0) {
                    counter++;
                }
            }

            return counter;

        }}

如您所见，我的解决方案运行完美，但在性能方面，由于时间复杂度 O(B-A)，它的得分为 0%。

我如何改进此代码以使其得分 100%？

Answer 1

使用循环是蛮力，而这样的挑战无法用蛮力完成。

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

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

整除的整数个数

提示

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

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

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