Calculating the Number of Pairs of elements in a List that produce a Sum divisible by 60 - reduce the Time Complexity

Question

There are many permutation optimization questions, but every one is different.

At a coding assignment recently, I was asked, given a list of numbers, to find how many pairs add up to a multiple of 60.

I've come up with was the following solution:

public int getPairs(List<Integer> nums){
  int result = 0;
  for(int i=0; i<nums.size(); i++){
   for(int j=i+1; j<nums.size(); j++) {
     if((nums.get(i)+nums.get(j))%60 == 0){
       result++
     }
   }
  }
  return result; 
}

This code was correct, however the testing software failed some hidden test cases where the list of nums was 10000 because of "time out", meaning that it took too long.

I've tried converting the List to an array first, to save on size() and get() method calls, but it did not help me.

I am very confused. Is this not the fastest way to go over all possible combinations?

If the question asked not for a multiple of 60, but to be 60, then I would sort the array first, and as soon as the sum is greater then 60, skip over the rest of the array, but this is not the case.

Also, it's strange that 10000 size array should time out. 10,000 x 10,000 is 100,000,000. Surely doing an two additions, a division, compare, and and compareToZero 100,000,000 should take less than a second on a modern processor.

Did I do something wrong, or is the testing software bugged?

Answer 1

Mistakes explained

This code was correct, however the testing software failed some hidden test cases where the list of nums was 10000 because of "time out", meaning that it took too long.

I would not say that the code is correct (since there's a flaw in it), rather you had no opportunity to see it failing on a small input.

In the inner for-loop you're initializing the staring value of the index j to i - int j = i. Which means at the first iteration of the inner loop, you're adding an element to itself: nums.get(i) + nums.get(j) and then checking whether it's divisible by 60.

That's might lead to invalid results. Inner loop should start with j = i + 1. With this fix, you'll get a correct brute-force solution.

The second issue - terminology.

What your code is counting are not Permutations, but Combinations of pairs of elements (it's not an academical spreading of hairs, the result would be different).

As a simple illustration, suppose the input is [1,2,3], and we need Combinations of pairs of elements that are divisible by 3. There's only one Combination: [1,2], but two Permutations: [1,2] and [2,1].

Because in your brute-force solution i < j always holds true, it's not capable of generating Permutations (since it doesn't revisit the same indices in the inner loop it can only consider [i,j], but not [j,i]), and it produces the number of Combinations.

Now when the problem statement is clarified: "Find the number of Combinations pairs that are divisible by the given number", let's get to the actual solution.

Solution

As @Joachim Sauer has pointed out in the comments, the first step in addressing this problem is to create an array of frequencies of array elements % 60 (like in the first phase of the Counting sort algorithm).

Then we have two cases:

• When considering remainder from divisions by 60 in the union ranges [1,29]∪[31,59] we need to calculate a Cartesian product of frequencies of the corresponding remainders and add it to the total. I.e. frequency(1)xfrequency(59), frequency(2)xfrequency(58), ... all the way up to frequency(29)xfrequency(31). Note that we shouldn't touch frequency(0) and frequency(30) (they need to be treated separately), we should not double count the product, i.e. we should not consider reversed combinations like frequency(59)xfrequency(1).

• Combinations frequency(0) and frequency(30) are a special case because we can combine them only with themselves. And for both cases, we need to calculate a Binomial coefficient according to the following formula:

Where n is the number of frequencies (for 0 or for 30), and k is the number of elements in the combination, which is always equal to 2.

That's how the implementation might look like (to simplify testing, divisor 60 is not hard-coded, but provided as a method parameter):

public static long getPairCount(List<Integer> list, int divisor) {
    int[] freq = new int[divisor]; // frequencies of modulus of array elements
    for (int next : list) freq[next % divisor]++;
    
    long count = 0;
    for (int left = 1, right = divisor - 1; left < divisor / 2 + divisor % 2; left++, right--) {
        count += ((long) freq[left]) * freq[right]; // a cartesian product gives a number of ways to form a pair
    }
    // Special cases: remainder 0 and remainder divisor / 2 - now with dialing with pure Combinations
    // and instead Cartesian product a Binomial coefficient needs to be calculated
    if (freq[0] > 1) count += binomialCoefficient(freq[0], 2 );
    if (divisor % 2 == 0 && freq[divisor / 2] > 1) count += binomialCoefficient(divisor / 2, 2 ); // should be only considered if divisor is
    return count;
}

public static long binomialCoefficient(int n, int k) {
    
    return factorial(n) / (k * factorial(n - k));
}

public static long factorial(int num) {
    long result = 1;
    for (int i = 1; i <= num; i++) result *= i;
    return result;
}

main()

public static void main(String[] args) {
    System.out.println(getPairCount(List.of(1, 2, 3), 3)); // [1, 2]
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5), 7)); // [2, 5] x 2, [3, 4] x 2
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5), 5)); // [2, 3] x 4, [1, 4] x 2
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5, 5), 5)); // [2, 3] x 4, [1, 4] x 2, [5, 5]
}

Output:

1   // [1, 2]
4   // [2, 5] x 2, [3, 4] x 2
6   // [2, 3] x 4, [1, 4] x 2
7   // [2, 3] x 4, [1, 4] x 2, [5, 5]