Minimum possible value T such that at most D Partitions of the Array having at most sum T is possible | Function to check if the array can be partitioned into atmost d subarray with sum atmost T ; Initial partition ; Current sum ; If current sum exceeds T ; Create a new partition ; If count of partitions exceed d ; Function to find the minimum possible value of T ; Stores the maximum and total sum of elements ; Maximum element ; Sum of all elements ; Calculate median T ; If atmost D partitions possible ; Check for smaller T ; Otherwise ; Check for larger T ; Print the minimum T required ; Driver code ; Function call
def possible ( T , arr , n , d ) : NEW_LINE INDENT partition = 1 ; NEW_LINE total = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT total = total + arr [ i ] ; NEW_LINE if ( total > T ) : NEW_LINE INDENT partition = partition + 1 ; NEW_LINE total = arr [ i ] ; NEW_LINE if ( partition > d ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT DEDENT return True ; NEW_LINE DEDENT def calcT ( n , d , arr ) : NEW_LINE INDENT mx = - 1 ; sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT mx = max ( mx , arr [ i ] ) ; NEW_LINE sum = sum + arr [ i ] ; NEW_LINE DEDENT lb = mx ; NEW_LINE ub = sum ; NEW_LINE while ( lb < ub ) : NEW_LINE INDENT T_mid = lb + ( ub - lb ) // 2 ; NEW_LINE if ( possible ( T_mid , arr , n , d ) == True ) : NEW_LINE INDENT ub = T_mid ; NEW_LINE DEDENT else : NEW_LINE INDENT lb = T_mid + 1 ; NEW_LINE DEDENT DEDENT print ( lb ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT d = 2 ; NEW_LINE arr = [ 1 , 1 , 1 , 1 , 1 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE calcT ( n , d , arr ) ; NEW_LINE DEDENT