Array algorithm performance kata

user_986437 0
Viewed 203

Trying to brash up algorithm development, with this one:


You are given an array of integers a and an integer k. Your task is to calculate the number of ways to pick two different indices i < j, such that a[i] + a[j] is divisible by k.

Example

For a = [1, 2, 3, 4, 5] and k = 3, the output should be solution(a, k) = 4.

this is my java solution:

long solution(int[] a, int k) {
    
    final BiPredicate<Integer, Integer> isDivisible = (x,y) -> (a[x] + a[y]) % k == 0;
    long counter = 0;
    for(int i = 0; i < a.length - 1; i++) {
        for(int j = i + 1; j < a.length; j++ ){
            if(isDivisible.test(i,j)) {
               counter++; 
            }
        }
    }
    return counter;
}

It passes all the tests expect the performance ones, there must be some more performat solution, any ideas ?

algorithm java
1 Answers

Your approach is a brute force solution and has a quadratic time complexity.

Here is an improvement:

Consider that the sum of two numbers is a multiple of k, when either

  • they both are multiples of k, or
  • The sum of the remainders when they are divided by k, is k.

If we can count how many numbers there are for each possible remainder, we can find how many there are of the complementary remainder, and take the product. At the end we need to halve this total count, as we also counted cases where i > j. The cases where the remainder is 0 or is half of k, need special attention, as there the product would include cases where i == j, so these need to be discarded.

Here is an implementation:

long solution(int[] a, int k) {
    final HashMap<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        int key = a[i] % k;
        count.put(key, count.getOrDefault(key, 0) + 1);
    }
    int counter = 0;
    for (Map.Entry<Integer, Integer> set : count.entrySet()) {
        int mod = set.getKey();
        int freq = set.getValue();
        counter += freq * (mod > 0 && k != 2*mod 
                          ? count.getOrDefault(k - mod, 0) 
                          : freq - 1);
    }
    return counter / 2;
}
user_54598390
Related