Maximum number of groups that can receive fresh donuts distributed in batches of size K | Java program for the above approach ; 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
import java . io . * ; import java . util . * ; class GFG { static HashMap < String , Integer > memo ; public static int dfs ( int [ ] V , int left , int K ) { int q = 0 ; String key = Arrays . toString ( V ) ; key += Integer . toString ( left ) ; if ( memo . containsKey ( key ) ) return memo . get ( key ) ; else if ( left == 0 ) { for ( int 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 ( int i = 1 ; i < K ; ++ i ) { if ( V [ i ] > 0 ) { V [ i ] -- ; int nleft = i <= left ? left - i : K + left - i ; q = Math . max ( q , dfs ( V , nleft , K ) ) ; V [ i ] ++ ; } } } memo . put ( key , q ) ; return q ; } public static int maxGroups ( int K , int [ ] arr ) { int V [ ] = new int [ K ] ; for ( int x : arr ) V [ x % K ] ++ ; memo = new HashMap < String , Integer > ( ) ; int ans = V [ 0 ] + dfs ( V , 0 , K ) ; return ans ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 , 4 , 5 , 6 } ; int K = 3 ; System . out . println ( maxGroups ( K , arr ) ) ; } }