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?

arrays algorithm
Edit
Report