CODEWITHSUNDEEP
arraysalgorithm
prashantgpt91
prashantgpt91

Reputation: 1795

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

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?

Upvotes: 8

Views: 2276

Answers (3)

Dave
Dave

Reputation: 9085

This can't be solved in better than O(n^2) for general input arrays because some inputs lead to O(n^2) different outputs. E.g., it's easy to construct an array where every pair of elements has a different separation.

The question makes more sense if it's asking for the number of pairs that have some specified separation. That can be done in linear time, and uses the fact that the array's sorted. Doesn't really make sense to give a sorted array if the best we can do is slower than sorting.

Upvotes: 1

Ivan Smirnov
Ivan Smirnov

Reputation: 4435

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.

Upvotes: 5

firefrorefiddle
firefrorefiddle

Reputation: 3805

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

Upvotes: 7

Related Questions