Minimum sum of absolute differences of pairs in a triplet from three arrays | Lower_bound function ; Function to find the value closest to K in the array A [ ] ; Initialize close value as the end element ; Find lower bound of the array ; If lower_bound is found ; If lower_bound is not the first array element ; If * ( it - 1 ) is closer to k ; Return closest value of k ; Function to find the minimum sum of abs ( arr [ i ] - brr [ j ] ) and abs ( brr [ j ] - crr [ k ] ) ; Sort the vectors arr and crr ; Initialize minimum as LET_MAX ; Traverse the array brr [ ] ; Stores the element closest to val from the array arr [ ] ; Stores the element closest to val from the array crr [ ] ; If sum of differences is minimum ; Update the minimum ; Print the minimum absolute difference possible ; Driver code ; Function Call
def lower_bound ( arr , key ) : NEW_LINE INDENT low = 0 ; NEW_LINE high = len ( arr ) - 1 ; NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 ; NEW_LINE if ( arr [ mid ] >= key ) : NEW_LINE INDENT high = mid ; NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 ; NEW_LINE DEDENT DEDENT return low ; NEW_LINE DEDENT def closestValue ( A , k ) : NEW_LINE INDENT close = A [ - 1 ] ; NEW_LINE it = lower_bound ( A , k ) ; NEW_LINE if ( it != len ( A ) ) : NEW_LINE INDENT close = A [ it ] ; NEW_LINE if ( it != 0 ) : NEW_LINE INDENT if ( ( k - A [ it - 1 ] ) < ( close - k ) ) : NEW_LINE INDENT close = A [ it - 1 ] ; NEW_LINE DEDENT DEDENT DEDENT return close ; NEW_LINE DEDENT def minPossible ( arr , brr , crr ) : NEW_LINE INDENT arr . sort ( ) ; NEW_LINE crr . sort ( ) ; NEW_LINE minimum = 10 ** 9 ; NEW_LINE for val in brr : NEW_LINE INDENT arr_close = closestValue ( arr , val ) ; NEW_LINE crr_close = closestValue ( crr , val ) ; NEW_LINE if ( abs ( val - arr_close ) + abs ( val - crr_close ) < minimum ) : NEW_LINE INDENT minimum = abs ( val - arr_close ) + abs ( val - crr_close ) ; NEW_LINE DEDENT DEDENT print ( minimum ) ; NEW_LINE DEDENT a = [ 1 , 8 , 5 ] ; NEW_LINE b = [ 2 , 9 ] ; NEW_LINE c = [ 5 , 4 ] ; NEW_LINE minPossible ( a , b , c ) ; NEW_LINE