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
function findSum ( arr , N , pt ) { var sum = 0 ; var i ; for ( i = 0 ; i < N ; i ++ ) { sum += Math . abs ( arr [ i ] - pt ) ; } return sum ; } function findPoint ( arr , N , K ) { var left ; if ( N % 2 == 1 ) { left = arr [ parseInt ( N / 2 ) ] ; } else { left = arr [ parseInt ( N / 2 ) - 1 ] + 1 ; } var right = arr [ N - 1 ] ; while ( left <= right ) { var mid = parseInt ( ( left + right ) / 2 ) ; var temp = findSum ( arr , N , mid ) ; if ( temp == K ) { document . write ( mid ) ; return ; } else if ( K < temp ) { right = mid - 1 ; } else { left = mid + 1 ; } } left = arr [ 0 ] ; right = arr [ parseInt ( N / 2 ) ] - 1 ; while ( left <= right ) { var mid = parseInt ( ( left + right ) / 2 ) ; var temp = findSum ( arr , N , mid ) ; if ( temp == K ) { document . write ( mid ) ; return ; } else if ( K > temp ) { right = mid - 1 ; } else { left = mid + 1 ; } } document . write ( " " ) ; } var arr = [ 1 , 3 , 6 , 7 , 11 ] ; var K = 18 ; var N = arr . length ; findPoint ( arr , N , K ) ;