CountDiv(Codility)挑战算法的性能问题 [英] Performance issue with CountDiv (Codility) challenge algorithm

问题描述

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

Needing some help with the algorithm i made to solve this codility challenge :

编写一个函数，给定三个整数 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%.

As you can see, my solution works perfectly but performance wise it's scoring 0% due to the time complexity O(B-A).

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

How can i improve this code to make it score 100%?

推荐答案

使用循环是蛮力，而像这样的挑战无法通过蛮力来完成.

Using a loop is brute-force, and challenges like this cannot be done with brute-force.

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

Which means you have to calculate the result. Challenges like this are more often a math question more than a programming question, so put you math hat on.

所以考虑一下.在整数范围内，计算有多少可以被 K 整除.如果我让你手动(允许使用简单的计算器)，而不使用计算机来计算暴力破解，你会怎么做?例如.求 111 和 999 之间能被 13

So think about it. In a range of integers, calculate how many are divisible by K. If I asked you to do this manually (using a simple calculator is allowed), without using a computer to brute-force it, how would you doing it? E.g. find how many integers between 111 and 999 that are divisible by 13

提示

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

Find the first number in the range that is divisible by K, and the last number in the range that is divisible by K. For the example above, that would be 117 and 988.

现在计算从第一个整数到最后一个整数有多少个整数可以被 K 整除，记住同时计算它们.那么，117 和 988 之间有多少个整数可以被 13 整除?

Now calculate how many integers are divisible by K from first to last integer, remembering to count both of them. So, how many integers between 117 and 988 are divisible by 13?

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

这篇关于CountDiv(Codility)挑战算法的性能问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！