Проблема с производительностью алгоритма проверки CountDiv (Codility)

Question

Требуется помощь с алгоритмом, который я сделал для решения этой проблемы кодификации:

Напишите функцию, которая по трем целым числам A, B и K возвращает количество целых чисел в диапазоне [A ..B], которые делятся на K. Например, для A = 6, B = 11 и K = 2 ваша функция должна возвращать 3, потому что в диапазоне [6..11] есть три числа, делящихся на 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;

        }}

Как видите, мое решение работает отлично, но с точки зрения производительности оно набирает 0% из-за временной сложности O (BA).

Как можно я улучшил этот код, чтобы он набрал 100%?

Answer 1

Использование al oop - это грубая сила, и подобные задачи не могут быть выполнены с помощью грубой силы.

Это означает, что вам нужно вычислить результат. Подобные задачи чаще представляют собой вопросы математики , а не вопросы программирования , так что наденьте математическую шляпу.

Так что подумайте об этом. В диапазоне целых чисел вычислите сколько делится на K. Если бы я попросил вас сделать это вручную, (можно использовать простой калькулятор) , без использования компьютера для перебора - заставить его, как бы вы это сделали? Например, найдите, сколько целых чисел от 111 до 999 делятся на 13

Подсказка

Найдите первое число в диапазоне, которое делится на K и последнее число в диапазоне, который делится на K. В приведенном выше примере это будет 117 и 988.

Теперь вычислите, сколько целых чисел делятся на K от первого до последнего. целое число, не забывая сосчитать их обоих. Итак, сколько целых чисел от 117 до 988 делятся на 13?

Answer 2

Одна из возможностей - воспользоваться преимуществом целочисленной арифметики c, чтобы избавиться от некоторых крайних случаев. Иногда A и B оба, ни одно, либо одно или другое делится на k. И простое их вычитание не поможет решить проблему. Таким образом, одно из решений - разделить каждую на k перед их вычитанием.

Скажем, k = 7, A = 12, and B = 54. 54/7 - 12/7 = 7 - 1 = 6 (14,21,28,35,42,49)

Но что, если A было 14?

54/7 - 14/7 = 7 - 2 = 5 (14,21,28,35,42,49) Ответ один. Итак, когда A делится на k, необходимо добавить 1.

Что, если A и B делятся на k?

56/7 - 14/7 = 8 - 2 = 6 = (14,21,28,34,42,49,56). Ответ снова, разовый, поэтому специальный случай деления A на k позаботится об этом, добавив 1

int result = (B/k - A/k) + ((A%k == 0) ? 1 : 0);