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 the following solution:

public static int getPairs(List<Integer> nums, int divisor) {
    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)) % divisor == 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?

CodePudding user response：

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's 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

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 implemenation 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 list 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  = factorial(freq[0]) / 2 * factorial(freq[0] - 2);
    if (divisor % 2 == 0 && freq[divisor / 2] > 1) count  = factorial(freq[0]) / 2 * factorial(freq[0] - 2); // should be only considered if divisor is
    return count;
}

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]

CodePudding user response：

get this code

 public static int getPairs(List<Integer> nums, int divisor) {
    int result = 0;
    for (int i = 0; i < nums.size(); i  ) {
        if (i == divisor) {
          result  ;
        } else {
          int j = 60 - i;
          if (nums.contains(j)) {
            result  ;
          }
        }
    }
    return result;
  }