Home Â» Technical Interview Questions Â» Array Interview Questions Â» Find Pair with Given Difference

# Find Pair with Given Difference

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

## Example

Input

arr[] = {120, 30, 70, 20, 5, 6},

difference(n) = 40

Output

[30, 70]

Explanation

Here the difference of 30 and 70 is equal to the value of n.

Input

arr[] = {120, 30, 70, 20, 5, 6},

difference(n) = 10

Output

[20, 30]

Explanation

Here the difference of 20 and 30 is equal to the value of n.

Input

arr = {120, 30, 70, 20, 5, 6},

difference(n) = 30

Output

No pair found with given difference

Explanation

Here no such pair of elements exist such that the difference between them is equal to n.

## Algorithm for Find Pair with Given Difference

Now we know the problem statement. So, quickly move to the algorithm part. We first sort the given array and then traverse the whole array. We take two pointers first at index 0 and second at index 1. Now if the difference between them is less than given diff then move the second pointer by 1. If the difference between them is greater than given diff then move the first pointer by 1. If the difference between the elements is same then count the answer. Finally, print the total number of counts.

1: Sort the given array first.

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

3: Run loop to find if array[j] â€“ array[i] = n,

• If array[j] â€“ array[i] = n, print array[j] and array[i].
• Check, If array[j] â€“ array[i] > n, increment i.
• If array[j] â€“ array[i] < n, increment j.

4: If the loop reaches the end. Then print â€˜no pair foundâ€™.

## C++ Program for Find Pair with Given Difference

```#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;
}```
`pair with difference 40 is: [30, 70]`

## Complexity Analysis

### Time Complexity

O(NLogN) where n is the size of the array. Here we use the inbuilt sort function which leads us to nlogn time complexity.

### Space Complexity

O(1) because we don’t create any extra space while calculating the result.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions