Maximum number of groups that can receive fresh donuts distributed in batches of size K | Stores the result of the same recursive calls ; Recursive function to find the maximum number of groups that will receive fresh donuts ; Store the result for the current state ; Store the key and check if it is present in the hashmap ; If already calculated ; If left is 0 ; Traverse the array [ ] arr ; Decrement arr [ i ] ; Update the maximum number of groups ; Increment arr [ i ] by 1 ; Otherwise , traverse the given array [ ] arr ; Decrement arr [ i ] ; Update the maximum number of groups ; Increment arr [ i ] by 1 ; Memoize the result and return it ; Function to find the maximum number of groups that will receive fresh donuts ; Stores count of remainder by K ; Traverse the array [ ] arr ; Hashmap to memoize the results ; Store the maximum number of groups ; Return the answer ; Driver Code
let memo ; function dfs ( V , left , K ) { let q = 0 ; let key = V . join ( " " ) ; key += left . toString ( ) ; if ( memo . has ( key ) ) return memo [ key ] ; else if ( left == 0 ) { for ( let i = 1 ; i < K ; ++ i ) if ( V [ i ] > 0 ) { V [ i ] -- ; q = Math . max ( q , 1 + dfs ( V , K - i , K ) ) ; V [ i ] ++ ; } } else { for ( let i = 1 ; i < K ; ++ i ) { if ( V [ i ] > 0 ) { V [ i ] -- ; let nleft = i <= left ? left - i : K + left - i ; q = Math . max ( q , dfs ( V , nleft , K ) ) ; V [ i ] ++ ; } } } if ( memo . has ( key ) ) memo [ key ] = q ; else memo [ key ] = q ; return q ; } function maxGroups ( K , arr ) { let V = new Array ( K ) ; V . fill ( 0 ) ; for ( let x = 0 ; x < arr . length ; x ++ ) V [ arr [ x ] % K ] ++ ; memo = new Map ( ) ; let ans = V [ 0 ] + dfs ( V , 0 , K ) ; return ans ; } let arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; let K = 3 ; document . write ( maxGroups ( K , arr ) ) ;