Check if all people can vote on two machines | Returns true if n people can vote using two machines in x time . ; dp [ i ] [ j ] stores maximum possible number of people among arr [ 0. . i - 1 ] can vote in j time . ; Find sum of all times ; Fill dp [ ] [ ] in bottom up manner ( Similar to knapsack ) . ; If remaining people can go to other machine . ; Driver code
function canVote ( a , n , x ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( x + 1 ) ; for ( let j = 0 ; j < x + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) sum += a [ i ] ; for ( let i = 1 ; i <= n ; i ++ ) for ( let j = 1 ; j <= x ; j ++ ) if ( a [ i ] <= j ) dp [ i ] [ j ] = Math . max ( dp [ i - 1 ] [ j ] , a [ i ] + dp [ i - 1 ] [ j - a [ i ] ] ) ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; return ( sum - dp [ n ] [ x ] <= x ) ; } let n = 3 , x = 4 ; let a = [ 2 , 4 , 2 ] ; if ( canVote ( a , n , x ) ) { document . write ( " " ) ; } else { document . write ( " " ) ; }