Performance issue with CountDiv (Codility) challenge algorithm

user_13499542 0
Viewed 790

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%?

testing sorting java performance
4 Answers

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

user_52211490

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);
user_15525340

My C# solution, based on @Andreas' brilliant one. This eventually got me to 100%. Most surprising (and perhaps wrong?) is that [0, 0, 11] needs to produce a result of 1, meaning that 0 is considered divisible by 11. You'll see I had to comment out an error catcher to allow B to be zero and get me to the "expected" answer. I was surprised that (0-0)/11 didn't produce a runtime error, but it didn't.

    public int solutionCountDiv4(int A, int B, int K)
    {
        //Errors
        if (K == 0)
            return 0;

        //if (B == 0)
        //    return 0;

        if (A > B)
            return 0;

        var first = 0;
        var last = 0;

        for (first = A; first <= B; first++)
        {
            if (first % K == 0)
                break;
        }
        for (last = B; last >= A; last--)
        {
            if (last % K == 0)
                break;
        }

        if (first > last)
            return 0;

        var result = (last - first) / K + 1;
        return result;
    }
user_34661550

my answer is this:

def solution(A, B, K):
    # write your code in Python 3.6
    return B//K - (A-1)//K
user_13328700
Related