ADVERTISEMENT
ADVERTISEMENT

Find a pair with a given difference

Here, we are going to see how to search a pair from an array having some particular difference using C++?
Submitted by Radib Kar, on January 27, 2021

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

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;
    }
}

Using STL:

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++ code 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
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.