Find Pair with Given Difference

Problem Statement

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’.

Implementation

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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int diff;
    cin>>diff;
    FindPair(a, n, diff);
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    //In the given array -> array[] of N N 
    //finding the pair with difference n
    public static int FindPair(int array[], int N, int difference)
    {
        //sort the given array
        Arrays.sort(array);
        int i = 0;  
        int j = 1;
        while(i<N && j<N)
        {
            if (i != j && array[j]-array[i] == difference)
            {
                System.out.println(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++;
            }
        }
        System.out.println("No pair found");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int diff ;
        diff = sr.nextInt();
        FindPair(arr,n,diff);
    } 
}

6 
5 20 3 2 50 80
78

2 80