Maximum number of groups that can receive fresh donuts distributed in batches of size K | C ++ 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 ; Store the maximum number of groups ; Return the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < string , int > memo ; int dfs ( int V [ ] , int left , int K ) { int q = 0 ; string key = " " ; for ( int i = 0 ; i < K ; i ++ ) { key = key + to_string ( V [ i ] ) ; } key += to_string ( left ) ; if ( memo . find ( key ) != memo . end ( ) ) return memo [ key ] ; else if ( left == 0 ) { for ( int i = 1 ; i < K ; ++ i ) if ( V [ i ] > 0 ) { V [ i ] -- ; q = 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 = max ( q , dfs ( V , nleft , K ) ) ; V [ i ] ++ ; } } } if ( memo . find ( key ) != memo . end ( ) ) memo [ key ] = q ; else memo [ key ] = q ; return q ; } int maxGroups ( int K , int arr [ ] ) { int V [ K ] ; memset ( V , 0 , sizeof ( V ) ) ; for ( int i = 0 ; i < 6 ; i ++ ) V [ arr [ i ] % K ] ++ ; int ans = V [ 0 ] + dfs ( V , 0 , K ) ; return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int K = 3 ; cout << maxGroups ( K , arr ) ; return 0 ; }