Maximum length possible by cutting N given woods into at least K pieces | Function to check if it is possible to cut woods into K pieces of length len ; Stores count of pieces having length equal to K ; Traverse wood [ ] array ; Update count ; Function to find the maximum value of L ; Stores minimum possible of L ; Stores maximum possible value of L ; Apply binary search over the range [ left , right ] ; Stores mid value of left and right ; If it is possible to cut woods into K pieces having length of each piece equal to mid ; Update left ; Update right ; Driver Code
def isValid ( wood , N , len , K ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT count += wood [ i ] // len NEW_LINE DEDENT return ( count >= K ) NEW_LINE DEDENT def findMaxLen ( wood , N , K ) : NEW_LINE INDENT left = 1 NEW_LINE right = max ( wood ) NEW_LINE while ( left <= right ) : NEW_LINE INDENT mid = left + ( right - left ) // 2 NEW_LINE if ( isValid ( wood , N , mid , K ) ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid - 1 NEW_LINE DEDENT DEDENT return right NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT wood = [ 5 , 9 , 7 ] NEW_LINE N = len ( wood ) NEW_LINE K = 4 NEW_LINE print ( findMaxLen ( wood , N , K ) ) NEW_LINE DEDENT