Home » Algorithms

Find a pair with a given difference

Find a pair with a given difference: In this tutorial, we will learn how to find a pair from an array having some particular difference using C++? By Radib Kar Last updated : August 10, 2023

Problem statement

Let's the array to be [-34, 45, 21, 18, 47] and the difference to be 13 the there is no pair found, but if the difference is 26 then the pair will be {21, 47}.

Solution approaches to find a pair with a given difference

Here, we will be discussing two approaches for solving the problem. One is brute force & other is an efficient one.

Bruteforce approach

In the brute force method, we need to find each pair and its difference to check whether the difference is the same as the input one or not. Since we need to find each pair difference thus the time complexity would be of O(n^2).

Below is the code snippet for the brute force method,

for(int i=0;i<arr.size();i++){
    for(int j=0;j<arr.size();j++){
        if(i!=j && abs(arr[i]-arr[j]) == diff){
            number1=arr[i];
            number2=arr[j];
            break;
        }
    }
}

Efficient approach

To solve this efficiently, we need to use the binary search approach. We will sort the array first. Then from left to right, we will be traversing. So say we are at position i, then we will search for the element arr[i]+diff on the right-hand side the element which is arr[i+1, n] via binary search. This will take time complexity of O(nlogn).

for(int i=0;i<n;i++){
    int index = my_binary_search(arr,i+1,n-1,arr[i]+d); 
    if(index !=-1){
        number1 = arr[i];
        number2 = arr[index];
        break;
    }
}

Standard template library approach

We can use the same above algorithm with STL like below,

for(int i=0;i<n;i++){
    //lower_bound & binary_search is the STL function
    //to cehck detail of their usage check our website articles
    int left = i+1;
    
    // it returns true if it finds the value within the range
    if(binary_search(arr.begin()+left,arr.end(),arr[i]+d)){
        number1 = arr[i];
        //lower_bound returns the index
        number2 = arr[lower_bound(arr.begin()+left,arr.end(),arr[i]+d)-arr.begin()];
        break;
    }
}

binary_search() & lower_bound() are the STL functions we have used here.

C++ program to find a pair with a given difference

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

//naive approach
void findDifferenceNaive(vector<int>& arr, int diff)
{
    cout << "..............Using naive search......\n";

    //O(n^2) time complexity

    int number1 = INT_MAX, number2 = INT_MAX;

    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size(); j++) {
            if (i != j && abs(arr[i] - arr[j]) == diff) {
                number1 = arr[i];
                number2 = arr[j];
                break;
            }
        }
    }
 
    if (number1 == INT_MAX && number2 == INT_MAX)
        cout << "No such pair found";
    else
        cout << "The pair is: " << number1 << " , " << number2 << "\n";

    return;
}

void findDifferenceEfficientSTL(vector<int>& arr, int d)
{
    cout << "..............Using efficeint approach with STL......\n";

    //O(nlogn) time complexity

    int closestSum = INT_MAX;
    sort(arr.begin(), arr.end());

    int number1 = INT_MAX, number2 = INT_MAX;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        //lower_bound & binary_search is the STL function
        //to cehck detail of their usage check our website articles
        int left = i + 1;
        // it returns true if it finds the value within the range
        if (binary_search(arr.begin() + left, arr.end(), arr[i] + d)) { 
            number1 = arr[i];
            //lower_bound returns the index
            number2 = arr[lower_bound(arr.begin() + left, arr.end(), arr[i] + d) - arr.begin()];
            break;
        }
    }

    if (number1 == INT_MAX && number2 == INT_MAX)
        cout << "No such pair found";
    else
        cout << "The pair is: " << number1 << " , " << number2 << "\n";
    return;
}

//binary search function
int my_binary_search(vector<int>& arr, int start, int end, int number)
{

    if (start > end)
        return -1;
    if (start == end) {

        if (arr[start] != number)
            return -1;
        else
            return start;
    }

    while (start <= end) {

        int mid = start + (end - start) / 2;

        if (arr[mid] == number)
            return mid;
        else if (arr[mid] > number) {
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    return -1;
}

void findDifferenceEfficient(vector<int>& arr, int d)
{
    cout << "..............Using efficeint approach......\n";

    //O(nlogn) time complexity

    int closestSum = INT_MAX;
    sort(arr.begin(), arr.end());

    int number1 = INT_MAX, number2 = INT_MAX;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        int index = my_binary_search(arr, i + 1, n - 1, arr[i] + d);
        if (index != -1) {
            number1 = arr[i];
            number2 = arr[index];
            break;
        }
    }

    if (number1 == INT_MAX && number2 == INT_MAX)
        cout << "No such pair found";
    else
        cout << "The pair is: " << number1 << " , " << number2 << "\n";
    return;
}

int main()
{
    cout << "Enter number of elements\n";
    int n;
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter the difference value\n";
    int d;
    cin >> d;

    //using navive approach
    findDifferenceNaive(arr, d);
    //using efficeint approach
    findDifferenceEfficient(arr, d);
    //using STL for binary search
    findDifferenceEfficientSTL(arr, d);

    return 0;
}

Output

Enter number of elements
5
Enter the elements
-34
45
21
18
47
Enter the difference value
26
..............Using naive search......
The pair is: 47 , 21
..............Using efficeint approach......
The pair is: 21 , 47
..............Using efficeint approach with STL......
The pair is: 21 , 47