# Find all pairs with given a difference

0
161

## Find all pair of elements in the given array with given difference. (array without duplicates).

### Example

Input array: [90, 70, 20, 80, 50, 25, 35, 15, 100, 150]
Pair of elements with difference 20 will print
90, 70 and 35, 15

## Algorithm 1

Time Complexity: O(N^2)

Run two loops such that select one element from the array. Starting from the index 0, and look forward in the array to get a pair with given difference.

a)Â Â Â  If we find the element then print them.
b)Â Â Â  Else print, not found.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int main()
{

int arr[] = {90, 70, 20, 80, 50, 25, 35 , 15, 100, 150};//array
int N = sizeof(arr)/sizeof(arr[0]);

int difference;
cin>>difference; // difference required between two elements

for(int i=0; i<N; i++)//select an element
{
for(int j=i+1; j<N; j++) // look forward in the array
if(abs(arr[i] - arr[j]) == difference)//if we get a pair with given difference then success
{
cout << "Pair exists with the given difference and the elements are : " << arr[i] <<"  "<<arr[j];
return 0;
}
}

cout <<"No such pair exists with given difference";

}``````

## Algorithm 2:

Time Complexity: O(NlogN)

Step 1 : First sort the given array. It takes O(NlogN).

Step 2 : In the same way as the first algorithm, for every element starting from first element, find the matching pair.

i)Â Â Â  Here we will use binary search to find the element.
ii)Â Â Â  for element a and given difference n we search for a + n.
Binary search takes O(NlogN), therefore time complexity is O(NlogN).

### Algorithm 2 working Example

Input array:

Find pair of elements with difference = 20

Apply Algorithm on the input array,

Step 1 :

Sort the array,
Sorted array:

Step 2 :

a = 15, difference (n) = 20
so, a + n = 35,
binary_search(35, input array) = True.
Print 15, 35. Move forward

Step 3 :
a = 20, difference (n) = 20
so, a + n = 40,
binary_search(40, input array) = False.
Move forward

Step 4 :
a = 35, difference (n) = 20
so, a + n = 55,
binary_search(55, input array) = False.
Move forward

Step 5 :
a = 70, difference (n) = 20
so, a + n = 90,
binary_search(90, input array) = True.
Print 70, 90. Move forward

Step 6 :
a = 90, difference (n) = 20
so, a + n = 110,
binary_search(110, input array) = False.
End Here.
Therefore, for the given input it prints:
70, 90 and 15, 35.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int main()
{

int arr[] = {90, 70, 20, 80, 50, 25, 35 , 15, 100, 150};//array
int N = sizeof(arr)/sizeof(arr[0]);

int difference;
cin>>difference; // difference required between two elements

sort(arr,arr+N); //sort the array in ascending order

for(int i = 0; i < N; i++)
{
if(binary_search(arr,arr+N,abs(difference + arr[i]))) // if b - a = X and both b and a exists in array so simply we can search for X + a to obtain b.
{
cout<<"Pair exists\n";
return 0;
}
}

cout <<"No such pair exists with given difference";

}``````

If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.