Find the minimum of maximum length of a jump required to reach the last island in exactly k jumps | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( int arr [ ] , int n , int dist , int k ) { int req = 0 ; int curr = 0 ; int prev = 0 ; for ( int 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 ; } int minDistance ( int arr [ ] , int n , int k ) { int l = 0 ; int h = arr [ n - 1 ] ; int ans = 0 ; while ( l <= h ) { int m = ( l + h ) / 2 ; if ( isPossible ( arr , n , m , k ) ) { ans = m ; h = m - 1 ; } else l = m + 1 ; } return ans ; } int main ( ) { int arr [ ] = { 2 , 15 , 36 , 43 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 2 ; cout << minDistance ( arr , n , k ) ; return 0 ; }