Searching and Sorting: Count all distinct pairs with difference equal to k

You are given an unsorted array, and an integer K.

You need to get all distinct pairs with difference equal to k.

Input: arr[] = {1, 5, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2} 

We can solve this problem by number of different methods as below:

Use 2 loops and check for the pairs.

Sort the array

Remove the duplicates from the array

Perform binary search for each element of the arr[i].

Do binary search, for arr[i] + k in subarray from i+1 to n-1.

If arr[i] + k found, increment count.

Return the count.

For sorting it will take O(nlogn)
For second step it will take O(nlogn)

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;


int count_pairs_with_diff_k_linear_search(int arr[], int n, int k)
{
    int count = 0;
     
    for (int i = 0; i < n; i++)
    {       
        for (int j = i+1; j < n; j++)
            if (arr[i] - arr[j] == k || arr[j] - arr[i] == k )
                  count++;
    }
    return count;
}

int binary_search(int arr[], int low, int high, int x)
{
    if (high >= low)
    {
        int mid = low + (high - low)/2;
        if (x == arr[mid])
            return mid;
        if (x > arr[mid])
            return binary_search(arr, (mid + 1), high, x);
        else
            return binary_search(arr, low, (mid -1), x);
    }
    return -1;
}
 
int count_pairs_with_diff_k_binary_search(int arr[], int n, int k)
{
    int count = 0, i;
    sort(arr, arr+n); 
    
    for (i = 0; i < n-1; i++)
        if (binary_search(arr, i+1, n-1, arr[i] + k) != -1)
            count++;
 
    return count;
}
 
int main()
{
    int arr[] =  {1, 5, 3, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << "Count of the pair with " << k <<" difference is by using linear search method = "
         << count_pairs_with_diff_k_linear_search(arr, n, k)<<endl;

    cout << "Count of the pair with " << k <<" difference is by using linear search method = "
         << count_pairs_with_diff_k_binary_search(arr, n, k)<<endl;

    return 0;
} 

Output:

Count of the pair with 3 difference is by using linear search method = 2
Count of the pair with 3 difference is by using linear search method = 2