Maximum number of groups that can receive fresh donuts distributed in batches of size K | Recursive function to find the maximum number of groups that will receive fresh donuts ; Store the result for the current state ; Check if the leftover donuts from the previous batch is 0 ; If true , then one by one give the fresh donuts to each group ; Decrement arr [ i ] ; Update the maximum number of groups ; Increment arr [ i ] ; Otherwise , traverse the given array , arr [ ] ; Decrement arr [ i ] ; Update the maximum number of groups ; Increment arr [ i ] ; Return the value of q ; Function to find the maximum number of groups that will receive fresh donuts ; Stores count of remainder by K ; Traverse the array arr [ ] ; Stores maximum number of groups ; Return the answer ; Driver Code
def dfs ( arr , left , K ) : NEW_LINE INDENT q = 0 NEW_LINE if ( left == 0 ) : NEW_LINE INDENT for i in range ( 1 , K , 1 ) : NEW_LINE INDENT if ( arr [ i ] > 0 ) : NEW_LINE INDENT arr [ i ] -= 1 NEW_LINE q = max ( q , 1 + dfs ( arr , K - i , K ) ) NEW_LINE arr [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT for i in range ( 1 , K , 1 ) : NEW_LINE INDENT if ( arr [ i ] > 0 ) : NEW_LINE INDENT arr [ i ] -= 1 NEW_LINE nleft = left - i if i <= left else K + left - i NEW_LINE q = max ( q , dfs ( arr , nleft , K ) ) NEW_LINE arr [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT return q NEW_LINE DEDENT def maxGroups ( K , arr , n ) : NEW_LINE INDENT V = [ 0 for i in range ( K ) ] NEW_LINE for x in range ( n ) : NEW_LINE INDENT V [ arr [ x ] % K ] += 1 NEW_LINE DEDENT ans = V [ 0 ] + dfs ( V , 0 , K ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE K = 3 NEW_LINE print ( maxGroups ( K , arr , n ) ) NEW_LINE DEDENT