text: Median of difference of all pairs from an Array | C ++ Program to implement the above approach ; Function check if mid can be median index of the difference array ; Size of the array ; Total possible no of pair possible ; The index of the element in the difference of all pairs from the array ; Count the number of pairs having difference <= mid ; If the difference between end and first element is less then or equal to mid ; Checking for the no of element less than or equal to mid is greater than median or not ; Function to calculate the median of differences of all pairs from the array ; Size of the array ; Initialising the low and high ; Binary search ; Calculate mid ; If mid can be the median of the array ; Returning the median of the differences of pairs from the array ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; bool possible ( ll mid , vector < ll > & a ) { ll n = a . size ( ) ; ll total = ( n * ( n - 1 ) ) / 2 ; ll need = ( total + 1 ) / 2 ; ll count = 0 ; ll start = 0 , end = 1 ; while ( end < n ) { if ( a [ end ] - a [ start ] <= mid ) { end ++ ; } else { count += ( end - start - 1 ) ; start ++ ; } } if ( end == n && start < end && a [ end - 1 ] - a [ start ] <= mid ) { ll t = end - start - 1 ; count += ( t * ( t + 1 ) / 2 ) ; } if ( count >= need ) return true ; else return false ; } ll findMedian ( vector < ll > & a ) { ll n = a . size ( ) ; ll low = 0 , high = a [ n - 1 ] - a [ 0 ] ; while ( low <= high ) { ll mid = ( low + high ) / 2 ; if ( possible ( mid , a ) ) high = mid - 1 ; else low = mid + 1 ; } return high + 1 ; } int main ( ) { vector < ll > a = { 1 , 7 , 5 , 2 } ; sort ( a . begin ( ) , a . end ( ) ) ; cout << findMedian ( a ) << endl ; }