Performance issue with CountDiv (Codility) challenge algorithm

Question

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

Write a function that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K. For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.
A and B are integers within the range [0..2,000,000,000]; K is an integer within the range [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;

        }}

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

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

Answer 1

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.

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

Hint

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.

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?

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

Answer 2

One possibility is to take advantage of integer arithmetic to get rid of some edge cases. Sometimes A and B are both, neither, or one or the other is divisible by k. And just subtracting them won't really help solve the problem. So one solution is to divide each by k before subtracting them.

Say k = 7, A = 12, and B = 54. 54/7 - 12/7 = 7 - 1 = 6 (14,21,28,35,42,49)

But what if A was 14?

54/7 - 14/7 = 7 - 2 = 5 (14,21,28,35,42,49) The answer is one off. So when A is divisible by k, 1 needs to be added.

What if A and B are both divisible by k?

56/7 - 14/7 = 8 - 2 = 6 = (14,21,28,34,42,49,56). The answer is again, one off, so the special case of A being divisible by k takes care of it by adding 1

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