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
memo = { } NEW_LINE def dfs ( V , left , K ) : NEW_LINE INDENT q = 0 NEW_LINE v = [ str ( int ) for int in V ] NEW_LINE key = " , " . join ( v ) NEW_LINE key += str ( left ) NEW_LINE if key in memo : NEW_LINE INDENT return memo [ key ] NEW_LINE DEDENT elif left == 0 : NEW_LINE INDENT for i in range ( 1 , K ) : NEW_LINE INDENT if V [ i ] > 0 : NEW_LINE INDENT V [ i ] -= 1 NEW_LINE q = max ( q , 1 + dfs ( V , K - i , K ) ) NEW_LINE V [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT for i in range ( 1 , K ) : NEW_LINE INDENT if V [ i ] > 0 : NEW_LINE INDENT V [ i ] -= 1 NEW_LINE if i <= left : NEW_LINE INDENT nleft = left - i NEW_LINE DEDENT else : NEW_LINE INDENT nleft = K + left - i NEW_LINE DEDENT q = max ( q , dfs ( V , nleft , K ) ) NEW_LINE V [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT if key in memo : NEW_LINE INDENT memo [ key ] = q NEW_LINE DEDENT else : NEW_LINE INDENT memo [ key ] = q NEW_LINE DEDENT return q NEW_LINE DEDENT def maxGroups ( K , arr ) : NEW_LINE INDENT V = [ 0 ] * ( K ) NEW_LINE for x in range ( len ( arr ) ) : NEW_LINE INDENT V [ arr [ x ] % K ] += 1 NEW_LINE DEDENT memo = { } NEW_LINE ans = V [ 0 ] + dfs ( V , 0 , K ) NEW_LINE return ans NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE K = 3 NEW_LINE print ( maxGroups ( K , arr ) ) NEW_LINE