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
function possible ( T , arr , n , d ) { let partition = 1 ; let total = 0 ; for ( let i = 0 ; i < n ; i ++ ) { total = total + arr [ i ] ; if ( total > T ) { partition = partition + 1 ; total = arr [ i ] ; if ( partition > d ) { return false ; } } } return true ; } function calcT ( n , d , arr ) { let mx = - 1 , sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) { mx = Math . max ( mx , arr [ i ] ) ; sum = sum + arr [ i ] ; } let lb = mx ; let ub = sum ; while ( lb < ub ) { let T_mid = lb + ( ub - lb ) / 2 ; if ( possible ( T_mid , arr , n , d ) == true ) { ub = T_mid ; } else { lb = T_mid + 1 ; } } document . write ( lb ) ; } let d = 2 ; let arr = [ 1 , 1 , 1 , 1 , 1 ] ; let n = arr . length ; calcT ( n , d , arr ) ;