Find a point whose sum of distances from all given points on a line is K | Java program for the above approach ; 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
import java . lang . * ; class GFG { public static int findSum ( int arr [ ] , int N , int pt ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += Math . abs ( arr [ i ] - pt ) ; } return sum ; } public static void findPoint ( int arr [ ] , int N , int K ) { int left ; if ( N % 2 != 0 ) { left = arr [ N / 2 ] ; } else { left = arr [ N / 2 - 1 ] + 1 ; } int right = arr [ N - 1 ] ; while ( left <= right ) { int mid = ( left + right ) / 2 ; int temp = findSum ( arr , N , mid ) ; if ( temp == K ) { System . out . println ( mid ) ; return ; } else if ( K < temp ) { right = mid - 1 ; } else { left = mid + 1 ; } } left = arr [ 0 ] ; right = arr [ N / 2 ] - 1 ; while ( left <= right ) { int mid = ( left + right ) / 2 ; int temp = findSum ( arr , N , mid ) ; if ( temp == K ) { System . out . println ( mid ) ; return ; } else if ( K > temp ) { right = mid - 1 ; } else { left = mid + 1 ; } } System . out . println ( " - 1" ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 3 , 6 , 7 , 11 } ; int K = 18 ; int N = arr . length ; findPoint ( arr , N , K ) ; } }