Problem Statement:
You are given an unsorted array, and an integer K.
You need to get all distinct pairs with difference equal to k.
Example
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}
Solution
We can solve this problem by number of different methods as below:
Method 1:
Use 2 loops and check for the pairs.
Time complexity O(n2)
Method 2 (Binary Search):
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.
Time complexity:
For sorting it will take O(nlogn)
For second step it will take O(nlogn)
Solution in C++
#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