Count all pairs with a given difference

Today's post is sort of an extension of previous post.

Here We will discuss approaches to count all distinct pairs with a given difference k.

Example to understand the question better:

Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2}

The algorithm is similar to the previous one only so, i will carry forward to the code. :)

Few points relating to aforementioned code:

1. The sorting can be done in nlog n time complexity.

2, Instead of binary search HASHING can also be used to find elements but time complexity will remain  O(n logn).

3, AVL Trees can also be used to counter this problem. Instead of sorting the elements an AVL tree can be made and maintained and for each element arr[i]+k can be searched in O(log n) time.But the overall time complexity will still remain O(n logn).

#include<stdio.h>
#include<stdlib.h>

int compare(const void* a,const void* b)
{
return (*(int*)a - *(int*)b);
}

int binarySearch(int arr[],int low,int high,int k)
{
    int mid= low+((high-low)/2);
    if(high>=low)
    {

    if(arr[mid]==k)
        return mid;
    if(arr[mid]>k)
        return binarySearch(arr,low,mid-1,k);
    if(arr[mid]<k)
        return binarySearch(arr,mid+1,high,k);
    }
    return -1;
}
void countPairs(int arr[], int n,int k)
{
    int i=0,pairs=0;
    qsort(arr,n,sizeof(int),compare); //for sorting the elements of the array
    for(i=0;i<n;i++)
       {
           if(binarySearch(arr,i+1,n-1,arr[i]+k)!=-1)
            pairs++;
       }

printf("No. of distinct pairs with difference as %d are %d",k,pairs);


}
int main()
{
    int arr[]= {1, 5, 3, 4, 2};
    int k=3;
    int n=sizeof(arr)/sizeof(arr[0]);
    countPairs(arr,n,k);
    return 0;

}

Comments and suggestions are welcome..:)

Viva La Raza

Sid