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
def isPossible ( arr , n , dist , k ) : NEW_LINE INDENT req = 0 NEW_LINE curr = 0 NEW_LINE prev = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT while ( curr != n and ( arr [ curr ] - arr [ prev ] ) <= dist ) : NEW_LINE INDENT curr = curr + 1 NEW_LINE DEDENT req = req + 1 NEW_LINE if ( curr == n ) : NEW_LINE INDENT break NEW_LINE DEDENT prev = curr - 1 NEW_LINE DEDENT if ( curr != n ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( req <= k ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def minDistance ( arr , n , k ) : NEW_LINE INDENT l = 0 NEW_LINE h = arr [ n - 1 ] NEW_LINE ans = 0 NEW_LINE while ( l <= h ) : NEW_LINE INDENT m = ( l + h ) // 2 ; NEW_LINE if ( isPossible ( arr , n , m , k ) ) : NEW_LINE INDENT ans = m NEW_LINE h = m - 1 NEW_LINE DEDENT else : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 2 , 15 , 36 , 43 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE print ( minDistance ( arr , n , k ) ) NEW_LINE