Find pair with given difference

In the given unsorted array, find the pair of elements in the given array with given difference n.

Example

a) Input array: [120, 30, 70, 20, 5, 6], difference(n) = 40
    Output = [30, 70], 70 -30 = 40

b) Input array: [120, 30, 70, 20, 5, 6], difference(n) = 10
    Output = [20, 30], 30 -20 = 10

c) Input array: [120, 30, 70, 20, 5, 6], difference(n) = 30
    Output: No pair found with given difference

Time complexity: O(NLogN)

Algorithm

Step 1: sort the given array first.

Step 2: In this array, take two indexes i and j initialize i = 0 and j = 1.

Step 3: Run loop to find if array[j] – array[i] = n,

               a) If array[j] – array[i] = n, print array[j] and array[i].

               b) If array[j] – array[i] > n, increment i.

               c) If array[j] – array[i] < n, increment j.

Step 4: If the loop reaches the end. Then print ‘no pair found’.

Algorithm Working

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
//In the given array -> array[] of N N 
//finding the pair with difference n
int FindPair(int array[], int N, int difference)
{
    //sort the given array
    sort(array, array+N);
    int i = 0;  
    int j = 1;
    while(i<N && j<N)
    {
        if (i != j && array[j]-array[i] == difference)
        {
            cout<<"pair with difference "<<difference<<" is: ";
            cout<<"["<<array[i]<<", "<<array[j]<<"]";
            return 1;
        }
        //if difference here is less than given difference
        // move right pointer(j)
        else if (array[j]-array[i] < difference) 
        {
            j++;
        }
        //if difference here is greater than given difference
        // move left pointer(i)
        else
        {
            i++;
        }
    }
    cout<<"No pair found";
    return 0;
}
 
//Main function to check above functions
int main()
{
    int input_array[] = {120, 30, 70, 20, 5, 6};
    int N = sizeof(input_array)/sizeof(int);
    int difference = 40;
    FindPair(input_array, N, difference);
    return 0;
}
Try It


Next > < Prev
Scroll to Top