2
\$\begingroup\$

pairs() is a function which returns the total number of combinations whose difference is k.

     static int pairs(int[] a,int k) {
        int counter=0;
         for (int i : a.length ) {
           for(int j=i+1;j<a.length;j++){
                 if(a[i]-a[j]==k||a[i]-a[j]==-k){
                   counter++;
                 }
                }
           }

 return counter;
}

a is an array of numbers and k is the difference of numbers that are given by user. I have to find the total number of combinations with a difference of k. I have done this code, but I want a more optimized code.

\$\endgroup\$
  • \$\begingroup\$ Could you add a couple of example inputs/outputs? \$\endgroup\$ – Simon Forsberg Aug 20 '15 at 15:49
  • 3
    \$\begingroup\$ for (int i : a.length ) this is a compiler error, which affects the rest of the code... \$\endgroup\$ – h.j.k. Aug 20 '15 at 15:59
10
\$\begingroup\$

Current complexity is \$O(n^2)\$, you can accomplish this with \$O(n \space log \space n)\$ instead by sorting the array first and then loop through the elements.

Let's say that you know that the array is sorted, and the array is for example 4 8 15 16 23 42 and you want to find the diff 7:

Let's initialize two variables, lowIndex, highIndex to both 0.

  • Now we compare index 0 to index 0, i.e. 4 and 4. It's less than the diff value (7) so we increase highIndex
  • Compare index 0 to index 1, 4 vs. 8, still less than 7, so highIndex++
  • Compare index 0 to index 2, 4 vs. 15, that's more than 7, so lowIndex++
  • Compare index 1 to index 2, 8 vs. 15, that's exactly 7, so we have a match and we do highIndex++
  • Compare index 1 to index 3, 8 vs. 16, that's more than 7, so lowIndex++
  • Compare index 2 to index 3, 15 vs. 16, that's less than 7, so highIndex++
  • Compare index 2 to index 4, 15 vs. 23, that's more than 7, so lowIndex++
  • Compare index 3 to index 4, 16 vs. 23, that's exactly 7, so we have a match and we do highIndex++
  • Compare index 3 to index 5, 16 vs. 42, that's more than 7, so lowIndex++
  • Compare index 4 to index 5, 23 vs. 42, that's more than 7, so lowIndex++
  • Compare index 5 to index 5, 42 vs. 42, that's less than 7, so highIndex++
  • highIndex has reached the end of the array, return the number of matches found.
\$\endgroup\$
  • \$\begingroup\$ You need the handle the case of elements being equal too, though. That means an array with 2x duplicates such as 4 4 8 8 15 15 16 16 23 23 42 42 should return 4x the number of combinations as without duplicates. \$\endgroup\$ – JS1 Aug 20 '15 at 17:03
  • \$\begingroup\$ @JS1 Right, that would be the next step. There are a few different ways to handle that, I think. \$\endgroup\$ – Simon Forsberg Aug 20 '15 at 17:57
3
\$\begingroup\$

I'm not a Java expert, but one suggestion would be to subtract once in the loop:

static int pairs(int[] a, int k) {
    int counter = 0;

    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            int diff = a[i] - a[j];
            if (diff == k || diff == -k) {
                counter++;
            }
        }
    }

    return counter;
}

This should not hurt performance, as you already do the subtraction no less than once, and in the case of a[i] being less than a[j] it should help performance.

You could also precompute -k to save on the negation of it. (Not that this is an expensive calculation.)

static int pairs(int[] a, int k) {
    int counter = 0;
    int negK = -k;

    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            int diff = a[i] - a[j];
            if (diff == k || diff == negK) {
                counter++;
            }
        }
    }

    return counter;
}

I can't guarantee that will have performance impacts, though.


Also, another note, the for (int i : a.length) does not appear to be valid Java.

The correct version is for (int i : a) (according to this Oracle document), which is not actually what you are trying to do. To fix that to match with the rest of your code, you should be using for (int i = 0; i < a.length; i++).


Lastly (and I already did this for you) you should definitely clean up the formatting of your code. It's very hard to read as it stands. Clearing up your indentation makes the code a lot easier to follow.

\$\endgroup\$
  • \$\begingroup\$ How about using Math.abs(diff) == k? \$\endgroup\$ – Simon Forsberg Aug 20 '15 at 15:58
  • \$\begingroup\$ @SimonAndréForsberg Something tells me that would be slower. A call to Math.abs cannot be free. (I don't have a Java environment setup, so I can't vouch whether or not it is.) \$\endgroup\$ – 410_Gone Aug 20 '15 at 15:59
  • \$\begingroup\$ Math.abs(diff) will come with another packages that wil degrade performance \$\endgroup\$ – Rahul Singh Aug 20 '15 at 16:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.