Find the minimum of maximum length of a jump required to reach the last island in exactly k jumps | Function that returns true if it is possible to reach end of the array in exactly k jumps ; Variable to store the number of steps required to reach the end ; If it is possible to reach the end in exactly k jumps ; Returns the minimum maximum distance required to reach the end of the array in exactly k jumps ; Stores the answer ; Binary search to calculate the result ; Driver code
< ? php function isPossible ( $ arr , $ n , $ dist , $ k ) { $ req = 0 ; $ curr = 0 ; $ prev = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { while ( $ curr != $ n && $ arr [ $ curr ] - $ arr [ $ prev ] <= $ dist ) $ curr ++ ; $ req ++ ; if ( $ curr == $ n ) break ; $ prev = $ curr - 1 ; } if ( $ curr != $ n ) return false ; if ( $ req <= $ k ) return true ; return false ; } function minDistance ( $ arr , $ n , $ k ) { $ l = 0 ; $ h = $ arr [ $ n - 1 ] ; $ ans = 0 ; while ( $ l <= $ h ) { $ m = floor ( ( $ l + $ h ) / 2 ) ; if ( isPossible ( $ arr , $ n , $ m , $ k ) ) { $ ans = $ m ; $ h = $ m - 1 ; } else $ l = $ m + 1 ; } return $ ans ; } $ arr = array ( 2 , 15 , 36 , 43 ) ; $ n = count ( $ arr ) ; $ k = 2 ; echo minDistance ( $ arr , $ n , $ k ) ; ? >