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

algorithm, arrays

Solution

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;
}

Problem

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?

Original source