Find a point whose sum of distances from all given points on a line is K | Function to find the sum of distances of all points from a given point ; Stores sum of distances ; Traverse the array ; Return the sum ; Function to find such a point having sum of distances of all other points from this point equal to K ; If N is odd keep left as arr [ n / 2 ] else keep left as arr [ n / 2 - 1 ] + 1 ; ; Keep right as arr [ N - 1 ] ; Perform binary search in the right half ; Calculate the mid index of the range ; If temp is equal to K ; Print the value of mid ; If the value of K < temp ; Update right to mid - 1 ; If the value of K > temp ; Update left to mid + 1 ; Update the value of left ; Update the value of right ; Perform binary search on the left half ; Calculate the mid index of the range ; If temp is equal to K ; Print mid ; if K > temp ; Update right to mid - 1 ; If K < temp ; Update left to mid + 1 ; If no such point found ; Driver Code
def findSum ( arr , N , pt ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += abs ( arr [ i ] - pt ) NEW_LINE DEDENT return sum NEW_LINE DEDENT def findPoint ( arr , N , K ) : NEW_LINE INDENT left = 0 NEW_LINE if ( N % 2 ) : NEW_LINE INDENT left = arr [ N // 2 ] NEW_LINE DEDENT else : NEW_LINE INDENT left = arr [ N // 2 - 1 ] + 1 NEW_LINE DEDENT right = arr [ N - 1 ] NEW_LINE while ( left <= right ) : NEW_LINE INDENT mid = ( left + right ) // 2 NEW_LINE temp = findSum ( arr , N , mid ) NEW_LINE if ( temp == K ) : NEW_LINE INDENT print ( mid ) NEW_LINE return NEW_LINE DEDENT elif ( K < temp ) : NEW_LINE INDENT right = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT DEDENT left = arr [ 0 ] NEW_LINE right = arr [ N // 2 ] - 1 NEW_LINE while ( left <= right ) : NEW_LINE INDENT mid = ( left + right ) // 2 NEW_LINE temp = findSum ( arr , N , mid ) NEW_LINE if ( temp == K ) : NEW_LINE INDENT print ( mid ) NEW_LINE return NEW_LINE DEDENT elif ( K > temp ) : NEW_LINE INDENT right = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT DEDENT print ( " - 1" ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 6 , 7 , 11 ] NEW_LINE K = 18 NEW_LINE N = len ( arr ) NEW_LINE findPoint ( arr , N , K ) NEW_LINE DEDENT