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.

READ  Partition Equal Subset Sum

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

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup