Find the number of couples with the same difference in a sorted array

Question

This is a interview Question.

"Given a sorted array. Find the number of couples with the same difference."

for example: if array is {1, 2, 3, 5, 7, 7 , 8, 9};

then we have

5 pairs with difference of 1

6 pairs with difference of 2

4 pairs with difference of 4

2 pairs with difference of 3

4 pairs with difference of 6

3 pairs with difference of 5

2 pairs with difference of 7

1 pair with difference of 8

1 pair with difference of 0

I tried the following:

maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
int b[maxdiff];
for(i=0;i<maxdiff;i++)
{
 for(j=0;j<n;j++)
 {
  p=arr[j]+i;
  x=binarysearch(p,arr);    //search p in array,where x return 0/1
  if(x==1)
  b[i]++;
 }
}

this is O(k*n*logn) solution where k is the maximum difference between the first and last element of a sorted array,n is the array size.

Does anyone have any better idea than this?

Answer 1

It seems unnecessarily complicated and I don't fully see what you are doing. Is the problem not solved by just:

maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
int b[maxdiff];
for(i=0;i<n;i++)
{
   for(j=0;j<i;j++) // note: <i instead of <n
   {
      b[arr[i]-arr[j]]++
   }
}

This is O(n**2).

BTW, you didn't list the one pair with a difference of 8 or the one pair with a difference of 0. On purpose?

Edit:

The logic is just: look at each pair in the original array. Each pair forms a difference. Increase the counter for that difference.

Edit 2:

On your request, here are my test results:

C:\src>a
diff: 0 pairs: 1
diff: 1 pairs: 5
diff: 2 pairs: 6
diff: 3 pairs: 2
diff: 4 pairs: 4
diff: 5 pairs: 3
diff: 6 pairs: 4
diff: 7 pairs: 2
diff: 8 pairs: 1

As well as the complete program:

#include <iostream>
using namespace std;

int main (int argc, char *argv[])
{
  int n=8;
  int arr[] = {1,2,3,5,7,7,8,9};
  int i, j;

  int maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
  int b[maxdiff];

  for(i=0;i<=maxdiff;i++)
    {
      b[i]=0;
    }  

  for(i=0;i<n;i++)
    {
      for(j=0;j<i;j++) // note: <i instead of <n
        {
          b[arr[i]-arr[j]]++;
        }
    }

  for (i=0;i<=maxdiff;++i)
    cout<<"diff: "<<i<<" pairs: "<<b[i]<<endl;
}

Answer 2

This can be solved in O(k*log k) (where k is a maximal difference) if you use Fourier transform for multiplication of polynomials.

Consider the following problem: having two sets A = a_1, ..., a_n and B = b_1, ..., b_m, for each X find the number of pairs (i, j) such that a_i + b_j = X. It can be solved as follows.

Let Pa = x**a_1 + ... + x**a_n, Pb = x**b_1 + ... + x**b_m. If you look at Pa * Pb, you may find that the coefficient for x**R is an answer for the problem where X = R. So, multiply this polynomials using Fourier transform, and you will find the answer for every X in O(n*log n).

Afterwards, your problem may be reduced to this one saying A = arr_1, ..., arr_n, B = -arr_1, ..., -arr_n and shifting (adding a constant) to every value of A and B to make them lay between 0 and k.