Saturday, September 3, 2011

Find the pair from an sorted array whose difference is x

Here is an inplace solution with O(n) complexity.

i=0,j=1;
while((i!=n-1) or j!=n)
{

  /*compare difference of a[j] and a[i]*/
  if( (a[j]-[a[i]])>x ) {
    i++;j++;
  }

  else if( (a[j]-a[i]) {
    j++;
  }

  else 
  {
  /*SOLUTION*/
  return;
  }

}

No comments:

Post a Comment