Count all disjoint pairs having absolute difference at least K from a given array
Given an array arr[] consisting of N integers, the task is to count all disjoint pairs having absolute difference of at least K.
Note: The pair (arr[i], arr[j]) and (arr[j], arr[i]) are considered as the same pair.
Examples:
Input: arr[] = {1, 3, 3, 5}, K = 2
Output: 2
Explanation:
The following two pairs satisfy the necessary conditions:
- {arr[0], arr[1]} = (1, 3) whose absolute difference is |1 – 3| = 2
- {arr[2], arr[3]} = (3, 5) whose absolute difference is |3 – 5| = 2
Input: arr[] = {1, 2, 3, 4}, K = 3
Output: 1
Explanation:
The only pair satisfying the necessary conditions is {arr[0], arr[3]} = (1, 4), since |1 – 4| = 3.
Naive Approach: The simplest approach is to generate all possible pairs of the given array and count those pairs whose absolute difference is at least K and to keep track of elements that have already been taken into pairs, using an auxiliary array visited[] to mark the paired elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count distinct pairs// with absolute difference atleast Kvoid countPairsWithDiffK(int arr[], int N, int K){ // Track the element that // have been paired int vis[N]; memset(vis, 0, sizeof(vis)); // Stores count of distinct pairs int count = 0; // Pick all elements one by one for (int i = 0; i < N; i++) { // If already visited if (vis[i] == 1) continue; for (int j = i + 1; j < N; j++) { // If already visited if (vis[j] == 1) continue; // If difference is at least K if (abs(arr[i] - arr[j]) >= K) { // Mark element as visited and // increment the count count++; vis[i] = 1; vis[j] = 1; break; } } } // Print the final count cout << count << ' ';}// Driver Codeint main(){ // Given arr[] int arr[] = { 1, 3, 3, 5 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Given difference K int K = 2; // Function Call countPairsWithDiffK(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to count distinct pairs// with absolute difference atleast Kstatic void countPairsWithDiffK(int arr[], int N, int K){ // Track the element that // have been paired int []vis = new int[N]; Arrays.fill(vis, 0); // Stores count of distinct pairs int count = 0; // Pick all elements one by one for(int i = 0; i < N; i++) { // If already visited if (vis[i] == 1) continue; for(int j = i + 1; j < N; j++) { // If already visited if (vis[j] == 1) continue; // If difference is at least K if (Math.abs(arr[i] - arr[j]) >= K) { // Mark element as visited and // increment the count count++; vis[i] = 1; vis[j] = 1; break; } } } // Print the final count System.out.print(count);}// Driver Codepublic static void main(String args[]){ // Given arr[] int arr[] = { 1, 3, 3, 5 }; // Size of array int N = arr.length; // Given difference K int K = 2; // Function Call countPairsWithDiffK(arr, N, K);}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approach# Function to count distinct pairs# with absolute difference atleast Kdef countPairsWithDiffK(arr, N, K): # Track the element that # have been paired vis = [0] * N # Stores count of distinct pairs count = 0 # Pick all elements one by one for i in range(N): # If already visited if (vis[i] == 1): continue for j in range(i + 1, N): # If already visited if (vis[j] == 1): continue # If difference is at least K if (abs(arr[i] - arr[j]) >= K): # Mark element as visited and # increment the count count += 1 vis[i] = 1 vis[j] = 1 break # Print the final count print(count)# Driver Codeif __name__ == '__main__': # Given arr[] arr = [ 1, 3, 3, 5 ] # Size of array N = len(arr) # Given difference K K = 2 # Function Call countPairsWithDiffK(arr, N, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to count distinct pairs// with absolute difference atleast Kstatic void countPairsWithDiffK(int[] arr, int N, int K){ // Track the element that // have been paired int[] vis = new int[N]; // Stores count of distinct pairs int count = 0; // Pick all elements one by one for(int i = 0; i < N; i++) { // If already visited if (vis[i] == 1) continue; for(int j = i + 1; j < N; j++) { // If already visited if (vis[j] == 1) continue; // If difference is at least K if (Math.Abs(arr[i] - arr[j]) >= K) { // Mark element as visited and // increment the count count++; vis[i] = 1; vis[j] = 1; break; } } } // Print the final count Console.Write(count);}// Driver Codepublic static void Main(){ // Given arr[] int[] arr = { 1, 3, 3, 5 }; // Size of array int N = arr.Length; // Given difference K int K = 2; // Function Call countPairsWithDiffK(arr, N, K);}}// This code is contributed by chitranayal |
Javascript
<script>// JavaScript implementation// for above approach// Function to count distinct pairs// with absolute difference atleast Kfunction countPairsWithDiffK(arr, N, K){ // Track the element that // have been paired var vis = new Array(N); vis.fill(0); // Stores count of distinct pairs var count = 0; // Pick all elements one by one for (var i = 0; i < N; i++) { // If already visited if (vis[i] == 1) continue; for (var j = i + 1; j < N; j++) { // If already visited if (vis[j] == 1) continue; // If difference is at least K if (Math.abs(arr[i] - arr[j]) >= K) { // Mark element as visited and // increment the count count++; vis[i] = 1; vis[j] = 1; break; } } } // Print the final count document.write( count + " ");} var arr = [ 1, 3, 3, 5 ]; // Size of array var N = arr.length; // Given difference K var K = 2; // Function Call countPairsWithDiffK(arr, N, K);// This code is contributed by SoumikMondal</script> |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The efficient idea is to use Binary Search to find the first occurrence having a difference of at least K. Below are the steps:
- Sort the given array in increasing order.
- Initialize cnt to 0 which will store the count of all possible pairs.
- Perform the Binary Search as per the following:
- Initialize left as 0 and right as N/2 + 1.
- Find the value of mid as (left + right) / 2.
- Check if mid number of pairs can be formed by pairing leftmost M elements with rightmost M elements i.e., check if arr[0] – arr[N – M] ? d, arr[1] – arr[N -M + 1] ? d, …, arr[M – 1] – arr[N – 1] ? d.
- In the above steps, traverse the array over the range [0, M] and if there exists an index whose abs(arr[N – M + i] – arr[i]) is less than K then update right as (mid – 1).
- Otherwise, update left as mid + 1 and cnt as mid.
- After the above step, print the value of cnt as all possible count of pairs.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible to// form M pairs with abs diff at least Kbool isValid(int arr[], int n, int m, int d){ // Traverse the array over [0, M] for (int i = 0; i < m; i++) { // If valid index if (abs(arr[n - m + i] - arr[i]) < d) { return 0; } } // Return 1 return 1;}// Function to count distinct pairs// with absolute difference atleast Kint countPairs(int arr[], int N, int K){ // Stores the count of all // possible pairs int ans = 0; // Initialize left and right int left = 0, right = N / 2 + 1; // Sort the array sort(arr, arr + N); // Perform Binary Search while (left < right) { // Find the value of mid int mid = (left + right) / 2; // Check valid index if (isValid(arr, N, mid, K)) { // Update ans ans = mid; left = mid + 1; } else right = mid - 1; } // Print the answer cout << ans << ' ';}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 3, 3, 5 }; // Given difference K int K = 2; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function call countPairs(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to check if it is possible to// form M pairs with abs diff at least Kstatic int isValid(int arr[], int n, int m, int d){ // Traverse the array over [0, M] for(int i = 0; i < m; i++) { // If valid index if (Math.abs(arr[n - m + i] - arr[i]) < d) { return 0; } } // Return 1 return 1;}// Function to count distinct pairs// with absolute difference atleast Kstatic void countPairs(int arr[], int N, int K){ // Stores the count of all // possible pairs int ans = 0; // Initialize left and right int left = 0, right = N / 2 + 1; // Sort the array Arrays.sort(arr); // Perform Binary Search while (left < right) { // Find the value of mid int mid = (left + right) / 2; // Check valid index if (isValid(arr, N, mid, K) == 1) { // Update ans ans = mid; left = mid + 1; } else right = mid - 1; } // Print the answer System.out.print(ans);}// Driver Codepublic static void main(String args[]){ // Given array arr[] int arr[] = { 1, 3, 3, 5 }; // Given difference K int K = 2; // Size of the array int N = arr.length; // Function call countPairs(arr, N, K);}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approach# Function to check if it is possible to# form M pairs with abs diff at least Kdef isValid(arr, n, m, d): # Traverse the array over [0, M] for i in range(m): # If valid index if (abs(arr[n - m + i] - arr[i]) < d): return 0 # Return 1 return 1# Function to count distinct pairs# with absolute difference atleast Kdef countPairs(arr, N, K): # Stores the count of all # possible pairs ans = 0 # Initialize left and right left = 0 right = N // 2 + 1 # Sort the array arr.sort(reverse = False) # Perform Binary Search while (left < right): # Find the value of mid mid = (left + right) // 2 # Check valid index if (isValid(arr, N, mid, K)): # Update ans ans = mid left = mid + 1 else: right = mid - 1 # Print the answer print(ans, end = "")# Driver Codeif __name__ == '__main__': # Given array arr[] arr = [ 1, 3, 3, 5 ] # Given difference K K = 2 # Size of the array N = len(arr) # Function call countPairs(arr, N, K)# This code is contributed by bgangwar59 |
C#
// C# program for the // above approachusing System;class GFG{ // Function to check if it // is possible to form M // pairs with abs diff at // least Kstatic int isValid(int []arr, int n, int m, int d){ // Traverse the array over // [0, M] for(int i = 0; i < m; i++) { // If valid index if (Math.Abs(arr[n - m + i] - arr[i]) < d) { return 0; } } // Return 1 return 1;}// Function to count distinct // pairs with absolute difference // atleast Kstatic void countPairs(int []arr, int N, int K){ // Stores the count of all // possible pairs int ans = 0; // Initialize left // and right int left = 0, right = N / 2 + 1; // Sort the array Array.Sort(arr); // Perform Binary Search while (left < right) { // Find the value of mid int mid = (left + right) / 2; // Check valid index if (isValid(arr, N, mid, K) == 1) { // Update ans ans = mid; left = mid + 1; } else right = mid - 1; } // Print the answer Console.WriteLine(ans);}// Driver Codepublic static void Main(){ // Given array arr[] int []arr = {1, 3, 3, 5}; // Given difference K int K = 2; // Size of the array int N = arr.Length; // Function call countPairs(arr, N, K);}}// This code is contributed by surendra_gangwar |
Javascript
<script>// javascript program for the above approach // Function to check if it is possible to // form M pairs with abs diff at least K function isValid(arr , n , m , d) { // Traverse the array over [0, M] for (i = 0; i < m; i++) { // If valid index if (Math.abs(arr[n - m + i] - arr[i]) < d) { return 0; } } // Return 1 return 1; } // Function to count distinct pairs // with absolute difference atleast K function countPairs(arr , N , K) { // Stores the count of all // possible pairs var ans = 0; // Initialize left and right var left = 0, right = N / 2 + 1; // Sort the array arr.sort(); // Perform Binary Search while (left < right) { // Find the value of mid var mid = parseInt((left + right) / 2); // Check valid index if (isValid(arr, N, mid, K) == 1) { // Update ans ans = mid; left = mid + 1; } else right = mid - 1; } // Print the answer document.write(ans); } // Driver Code // Given array arr var arr = [ 1, 3, 3, 5 ]; // Given difference K var K = 2; // Size of the array var N = arr.length; // Function call countPairs(arr, N, K);// This code contributed by gauravrajput1 </script> |
Output
2
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
