Given an array arr[] of length N, the task is to find the median of the differences of all pairs of the array elements.
Example:
Input: arr[] = {1, 2, 3, 4}
Output: 1
Explanation:
The difference of all pairs from the given array are {2 – 1, 3 – 2, 4 – 3, 3 – 1, 4 – 2, 4 – 1} = {1, 1, 1, 2, 2, 3}.
Since the array contains 6 elements, the median is the element at index 3 of the difference array.
Therefore, the answer is 1.
Input: arr[] = {1, 3, 5}
Output: 2
Explanation: The difference array is {2, 2, 4}. Therefore, the median is 2.
Naive Approach: The task is to generate all possible pairs from the given array and calculate the difference of every pair in the array arr[] and store them in the array diff[]. Sort diff[] and find the middle element.
Time Complexity: O(N2*log(N2))
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized using Binary Search and Sorting. Follow the below steps to solve the problem:
- Sort the given array.
- Initialize low=0 and high=arr[N-1]-arr[0].
- Calculate mid-equal to (low + high) / 2.
- Calculate the number of differences less than mid. If it exceeds the median index of the difference array, [ceil(N * (N – 1) / 2)], then update high as mid – 1. Otherwise, update low as mid + 1.
- Repeat the above steps until low and high becomes equal.
Below is the implementation above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> #define ll long long using namespace std; // Function check if mid can be median // index of the difference array bool possible(ll mid, vector<ll>& a) { // Size of the array ll n = a.size(); // Total possible no of pair // possible ll total = (n * (n - 1)) / 2; // The index of the element in the // difference of all pairs // from the array ll need = (total + 1) / 2; ll count = 0; ll start = 0, end = 1; // Count the number of pairs // having difference <= mid while (end < n) { if (a[end] - a[start] <= mid) { end++; } else { count += (end - start - 1); start++; } } // If the difference between end // and first element is less than // or equal to mid if (end == n && start < end && a[end - 1] - a[start] <= mid) { ll t = end - start - 1; count += (t * (t + 1) / 2); } // Checking for the no of element less than // or equal to mid is greater than median or // not if (count >= need) return true; else return false; } // Function to calculate the median // of differences of all pairs // from the array ll findMedian(vector<ll>& a) { // Size of the array ll n = a.size(); // Initialising the low and high ll low = 0, high = a[n - 1] - a[0]; // Binary search while (low <= high) { // Calculate mid ll mid = (low + high) / 2; // If mid can be the median // of the array if (possible(mid, a)) high = mid - 1; else low = mid + 1; } // Returning the median of the // differences of pairs from // the array return high + 1; } // Driver Code int main() { vector<ll> a = { 1, 7, 5, 2 }; sort(a.begin(), a.end()); cout << findMedian(a) << endl; } |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function check if mid can be median // index of the difference array static boolean possible(long mid, int[] a) { // Size of the array long n = a.length; // Total possible no of pair // possible long total = (n * (n - 1)) / 2; // The index of the element in the // difference of all pairs // from the array long need = (total + 1) / 2; long count = 0; long start = 0, end = 1; // Count the number of pairs // having difference <= mid while (end < n) { if (a[(int)end] - a[(int)start] <= mid) { end++; } else { count += (end - start - 1); start++; } } // If the difference between end // and first element is less than // or equal to mid if (end == n && start < end && a[(int)end - 1] - a[(int)start] <= mid) { long t = end - start - 1; count += (t * (t + 1) / 2); } // Checking for the no of element less than // or equal to mid is greater than median or // not if (count >= need) return true; else return false; } // Function to calculate the median // of differences of all pairs // from the array static long findMedian(int[] a) { // Size of the array long n = a.length; // Initialising the low and high long low = 0, high = a[(int)n - 1] - a[0]; // Binary search while (low <= high) { // Calculate mid long mid = (low + high) / 2; // If mid can be the median // of the array if (possible(mid, a)) high = mid - 1; else low = mid + 1; } // Returning the median of the // differences of pairs from // the array return high + 1; }// Driver codepublic static void main (String[] args){ int[] a = { 1, 7, 5, 2 }; Arrays.sort(a); System.out.println(findMedian(a));}}// This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function check if mid can be median # index of the difference array def possible(mid, a): # Size of the array n = len(a); # Total possible no of pair # possible total = (n * (n - 1)) // 2; # The index of the element in the # difference of all pairs # from the array need = (total + 1) // 2; count = 0; start = 0; end = 1; # Count the number of pairs # having difference <= mid while (end < n): if (a[end] - a[start] <= mid): end += 1; else: count += (end - start - 1); start += 1; # If the difference between end # and first element is less than # or equal to mid if (end == n and start < end and a[end - 1] - a[start] <= mid): t = end - start - 1; count += (t * (t + 1) // 2); # Checking for the no of element # less than or equal to mid is # greater than median or not if (count >= need): return True; else: return False; # Function to calculate the median # of differences of all pairs # from the array def findMedian(a): # Size of the array n = len(a); # Initialising the low and high low = 0; high = a[n - 1] - a[0]; # Binary search while (low <= high): # Calculate mid mid = (low + high) // 2; # If mid can be the median # of the array if (possible(mid, a)): high = mid - 1; else : low = mid + 1; # Returning the median of the # differences of pairs from # the array return high + 1; # Driver Code if __name__ == "__main__" : a = [ 1, 7, 5, 2 ]; a.sort() print(findMedian(a)); # This code is contributed by AnkitRai01 |
C#
// C# program to implement // the above approach using System;class GFG{// Function check if mid can be median // index of the difference array static bool possible(long mid, int[] a) { // Size of the array long n = a.Length; // Total possible no of pair // possible long total = (n * (n - 1)) / 2; // The index of the element in the // difference of all pairs // from the array long need = (total + 1) / 2; long count = 0; long start = 0, end = 1; // Count the number of pairs // having difference <= mid while (end < n) { if (a[(int)end] - a[(int)start] <= mid) { end++; } else { count += (end - start - 1); start++; } } // If the difference between end // and first element is less than // or equal to mid if (end == n && start < end && a[(int)end - 1] - a[(int)start] <= mid) { long t = end - start - 1; count += (t * (t + 1) / 2); } // Checking for the no of element less than // or equal to mid is greater than median or // not if (count >= need) return true; else return false; } // Function to calculate the median // of differences of all pairs // from the array static long findMedian(int[] a) { // Size of the array long n = a.Length; // Initialising the low and high long low = 0, high = a[(int)n - 1] - a[0]; // Binary search while (low <= high) { // Calculate mid long mid = (low + high) / 2; // If mid can be the median // of the array if (possible(mid, a)) high = mid - 1; else low = mid + 1; } // Returning the median of the // differences of pairs from // the array return high + 1; }// Driver codepublic static void Main (string[] args){ int[] a = { 1, 7, 5, 2 }; Array.Sort(a); Console.Write(findMedian(a));}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript Program to implement // the above approach // Function check if mid can be median // index of the difference array function possible(mid, a) { // Size of the array let n = a.length; // Total possible no of pair // possible let total = parseInt((n * (n - 1)) / 2); // The index of the element in the // difference of all pairs // from the array let need = parseInt((total + 1) / 2); let count = 0; let start = 0, end = 1; // Count the number of pairs // having difference <= mid while (end < n) { if (a[end] - a[start] <= mid) { end++; } else { count += (end - start - 1); start++; } } // If the difference between end // and first element is less than // or equal to mid if (end == n && start < end && a[end - 1] - a[start] <= mid) { let t = end - start - 1; count += parseInt(t * (t + 1) / 2); } // Checking for the no of element less than // or equal to mid is greater than median or // not if (count >= need) return true; else return false; } // Function to calculate the median // of differences of all pairs // from the array function findMedian(a) { // Size of the array let n = a.length; // Initialising the low and high let low = 0, high = a[n - 1] - a[0]; // Binary search while (low <= high) { // Calculate mid let mid = (low + high) / 2; // If mid can be the median // of the array if (possible(mid, a)) high = mid - 1; else low = mid + 1; } // Returning the median of the // differences of pairs from // the array return high + 1; } // Driver Code let a = [ 1, 7, 5, 2 ]; a.sort(); document.write(findMedian(a));</script> |
Output:
3
Time Complexity: O(N*log(M)), where N is the number of elements and M is the maximum difference among pairs of elements of an array.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
