Finding number of number pairs with given difference [closed]

Question

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.

Answer 1

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.

Answer 2

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.