Count of all pairs in an Array with minimum absolute difference
Given an integer array arr[] of size N, the task is to count the total number of distinct pairs having minimum absolute difference.
Examples:
Input: arr[] = {4, 2, 1, 3}
Output: 3
Explanation:
The minimum absolute difference between the pairs {1, 2}, {2, 3}, {3, 4} is 1.
Input: arr[] = {1, 3, 8, 10, 15}
Output: 2
Explanation:
The minimum absolute difference between the pairs {1, 3}, {8, 10} is 2.
Approach: The idea is to count the frequency of the minimum absolute difference of the adjacent elements of the sorted elements of the given array. Follow the steps below to solve the problem:
- Sort the given array arr[].
- Compare all adjacent pairs in the sorted array and find the minimum absolute difference between all adjacent pairs.
- Finally, count all the adjacent pairs having difference equal to minimum difference.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the count of all // pairs having minimal absolute difference int numberofpairs( int arr[], int N) { // Stores the count of pairs int answer = 0; // Sort the array sort(arr, arr + N); // Stores the minimum difference // between adjacent pairs int minDiff = INT_MAX; for ( int i = 0; i < N - 1; i++) // Update the minimum // difference between pairs minDiff = min(minDiff, arr[i + 1] - arr[i]); for ( int i = 0; i < N - 1; i++) { if (arr[i + 1] - arr[i] == minDiff) // Increase count of // pairs with difference // equal to that of // minimum difference answer++; } // Return the final count return answer; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 2, 1, 3 }; int N = ( sizeof arr) / ( sizeof arr[0]); // Function Call cout << numberofpairs(arr, N) << "\n" ; return 0; } |
Java
// Java program for the above import java.util.Arrays; class GFG{ // Function to return the count of all // pairs having minimal absolute difference static int numberofpairs( int []arr, int N) { // Stores the count of pairs int answer = 0 ; // Sort the array Arrays.sort(arr); // Stores the minimum difference // between adjacent pairs int minDiff = 10000000 ; for ( int i = 0 ; i < N - 1 ; i++) // Update the minimum // difference between pairs minDiff = Math.min(minDiff, arr[i + 1 ] - arr[i]); for ( int i = 0 ; i < N - 1 ; i++) { if (arr[i + 1 ] - arr[i] == minDiff) // Increase count of // pairs with difference // equal to that of // minimum difference answer++; } // Return the final count return answer; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4 , 2 , 1 , 3 }; int N = arr.length; // Function Call System.out.print(numberofpairs(arr, N)); } } // This code is contributed by rock_cool |
Python3
# Python3 program to implement # the above approach # Function to return the count of all # pairs having minimal absolute difference def numberofpairs(arr, N): # Stores the count of pairs answer = 0 # Sort the array arr.sort() # Stores the minimum difference # between adjacent pairs minDiff = 10000000 for i in range ( 0 , N - 1 ): # Update the minimum # difference between pairs minDiff = min (minDiff, arr[i + 1 ] - arr[i]) for i in range ( 0 , N - 1 ): if arr[i + 1 ] - arr[i] = = minDiff: # Increase count of pairs # with difference equal to # that of minimum difference answer + = 1 # Return the final count return answer # Driver code if __name__ = = '__main__' : # Given array arr[] arr = [ 4 , 2 , 1 , 3 ] N = len (arr) # Function call print (numberofpairs(arr,N)) # This code is contributed by virusbuddah_ |
C#
// C# program for the above approach using System; class GFG{ // Function to return the count of all // pairs having minimal absolute difference static int numberofpairs( int []arr, int N) { // Stores the count of pairs int answer = 0; // Sort the array Array.Sort(arr); // Stores the minimum difference // between adjacent pairs int minDiff = 10000000; for ( int i = 0; i < N - 1; i++) // Update the minimum // difference between pairs minDiff = Math.Min(minDiff, arr[i + 1] - arr[i]); for ( int i = 0; i < N - 1; i++) { if (arr[i + 1] - arr[i] == minDiff) // Increase count of // pairs with difference // equal to that of // minimum difference answer++; } // Return the final count return answer; } // Driver Code public static void Main(String[] args) { // Given array arr[] int []arr = { 4, 2, 1, 3 }; int N = arr.Length; // Function Call Console.Write(numberofpairs(arr, N)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for the above approach // Function to return the count of all // pairs having minimal absolute difference function numberofpairs(arr, N) { // Stores the count of pairs let answer = 0; // Sort the array arr.sort(); // Stores the minimum difference // between adjacent pairs let minDiff = Number.MAX_VALUE; for (let i = 0; i < N - 1; i++) // Update the minimum // difference between pairs minDiff = Math.min(minDiff, arr[i + 1] - arr[i]); for (let i = 0; i < N - 1; i++) { if (arr[i + 1] - arr[i] == minDiff) // Increase count of // pairs with difference // equal to that of // minimum difference answer++; } // Return the final count return answer; } // Given array arr[] let arr = [ 4, 2, 1, 3 ]; let N = arr.length; // Function Call document.write(numberofpairs(arr, N)); </script> |
Output:
3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)