Find a Pair with a given difference k

Happy new year Everyone.. :) Lets start coding..

Today's post is all about finding a pair of numbers in a given unsorted array, which has a difference k.

The simplest approach can be to run two loops.The Outer loops picks each element one by one and run an inner loop to compare it with each element and find if the difference between them is k.
Complexity: O(n^2)

Can we improve it... Yes.

Algorithm#1:

1. The array can be first sorted.  // complexity n logn
2. Binary search can be implemented for each element to find arr[i]+k in [i+1...n-1]. //complexity n log n

Complexity: O(n logn)

can we improve further ..Yes..

The second step can be improved to O(n). Lets see the approach.

Maintain two variables i=0 and j=1, initialize them respectively  Calculate their difference, if the diff is less than k, then increment j else increment i, till we get the exact difference or we run out of numbers.... :)

Simple yet intuitive approach..
Lets code it..

#include<stdio.h>

void findPair(int arr[],int n,int k)
{
    int i=0,j=1;

    while(i<n && j<n)
    {
        if(i!=j && arr[i]-arr[j]==k || arr[j]-arr[i]==k)
        {
            printf("Pair found %d %d",arr[i],arr[j]);
            //i++;
            return;
        }

        if(arr[j]-arr[i] > k)
            i++;
        else if(arr[j]-arr[i] < k)
            j++;

    }
    printf("No pair found");
}
int main()
{
    int arr[] = {1, 8, 30, 40, 100,160};
    int k=60,n;
    n=sizeof(arr)/sizeof(arr[0]);
    findPair(arr,n,k);
    return 0;
}

Comments and suggestions are welcome.. :)

Viva La Raza

Sid