Maximum number of groups that can receive fresh donuts distributed in batches of size K
Given an array arr[] consisting of N positive integers such that arr[i] denotes the size of the ith group sitting in a donut shop and a positive integer K, which denotes the maximum number of donuts that can be served in a batch, the task is to find the maximum number of groups that can receive fresh donuts if the customers of the same group are served together.
Note: All the customers in a group do not receive leftover donuts from the previous batch.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 4
Explanation: One possible way for the ordering of the groups is {6, 2, 4, 5, 1, 3}.
- arr[0](= 6), The shops serve two batches of 3 donuts. So everyone gets fresh donuts.
- arr[1](= 2), The shop serves 3 fresh donuts, among which 1 gets left out. So everyone gets fresh donuts.
- arr[2](= 4), The shop serves first 1 leftover donut and then serves 3 fresh donuts.
- arr[1](= 5), The shop serves 6 fresh donuts, among which 1 is left out. So everyone gets fresh donuts.
- arr[1](= 1), The shop serves 1 leftover donut.
- arr[1](= 3), The shop serves 3 fresh donuts. So everyone gets fresh donuts.
Therefore, a total of 4 groups get fresh donuts which is the maximum possible number of groups.
Input: arr[] = {1, 3, 2, 5, 2, 2, 1, 6}, K = 4
Output: 4
Naive Approach: The given problem can be solved by using backtracking for all possible ordering based on the observation that the remainder of each group size by K, needs only to be considered. Follow the steps below to solve the problem:
- Initialize an array, say V[] of size K, where V[i] denotes the number of groups with i people remaining.
- Traverse the array, arr[] using the variable i and for each arr[i], increment the value of V[arr[i] % K] by 1.
- Define a recursive function say dfs(V, left) to where left is the number of leftover donuts from the previous batch:
- Initialize a variable, res as 0, to store the result of the current state.
- If the value of left is 0, then iterate in the range [1, K – 1] using the variable i and perform the following steps:
- Decrement the value of V[i] by 1 and recursively call the function with argument left-i.
- Update res to the maximum of dfs(V, left – i) + 1 and res.
- Increment the value of V[i] by 1 for the backtracking step.
- Otherwise, repeat the same steps as above, but in this case, do not add 1 to the result, since the selected group will get the leftover donut.
- Return the value of res.
- Call the recursive function defined above as dfs(V, 0) and store the returned value in a variable, say X.
- Finally, after completing the above steps, print the sum of V[0] and X as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Recursive function to find the // maximum number of groups that // will receive fresh donuts int dfs( int arr[], int left, int K) { // Store the result for the // current state int q = 0; // Check if the leftover donuts // from the previous batch is 0 if (left == 0) { // If true, then one by one // give the fresh donuts // to each group for ( int i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; // Update the maximum // number of groups q = max(q, 1 + dfs(arr, K - i, K)); // Increment arr[i] arr[i]++; } } } // Otherwise, traverse the given // array, arr[] else { for ( int i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; int nleft = (i <= left ? left - i : K + left - i); // Update the maximum // number of groups q = max(q, dfs(arr, nleft, K)); // Increment arr[i] arr[i]++; } } } // Return the value of q return q; } // Function to find the maximum // number of groups that will // receive fresh donuts int maxGroups( int K, int arr[], int n) { // Stores count of remainder // by K int V[K] = { 0 }; // Traverse the array arr[] for ( int x = 0; x < n; x++) V[arr[x] % K]++; // Stores maximum number of groups int ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int K = 3; cout << maxGroups(K, arr, n); return 0; } // This code is contributed by Potta Lokesh |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Recursive function to find the // maximum number of groups that // will receive fresh donuts public static int dfs( int [] arr, int left, int K) { // Store the result for the // current state int q = 0 ; // Check if the leftover donuts // from the previous batch is 0 if (left == 0 ) { // If true, then one by one // give the fresh donuts // to each group for ( int i = 1 ; i < K; ++i) { if (arr[i] > 0 ) { // Decrement arr[i] arr[i]--; // Update the maximum // number of groups q = Math.max( q, 1 + dfs(arr, K - i, K)); // Increment arr[i] arr[i]++; } } } // Otherwise, traverse the given // array, arr[] else { for ( int i = 1 ; i < K; ++i) { if (arr[i] > 0 ) { // Decrement arr[i] arr[i]--; int nleft = (i <= left ? left - i : K + left - i); // Update the maximum // number of groups q = Math.max(q, dfs(arr, nleft, K)); // Increment arr[i] arr[i]++; } } } // Return the value of q return q; } // Function to find the maximum // number of groups that will // receive fresh donuts public static int maxGroups( int K, int [] arr) { // Stores count of remainder // by K int V[] = new int [K]; // Traverse the array arr[] for ( int x : arr) V[x % K]++; // Stores maximum number of groups int ans = V[ 0 ] + dfs(V, 0 , K); // Return the answer return ans; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 }; int K = 3 ; System.out.println( maxGroups(K, arr)); } } |
Python3
# Python 3 program for the above approach # Recursive function to find the # maximum number of groups that # will receive fresh donuts def dfs(arr, left, K): # Store the result for the # current state q = 0 # Check if the leftover donuts # from the previous batch is 0 if (left = = 0 ): # If true, then one by one # give the fresh donuts # to each group for i in range ( 1 ,K, 1 ): if (arr[i] > 0 ): # Decrement arr[i] arr[i] - = 1 # Update the maximum # number of groups q = max (q, 1 + dfs(arr, K - i, K)) # Increment arr[i] arr[i] + = 1 # Otherwise, traverse the given # array, arr[] else : for i in range ( 1 ,K, 1 ): if (arr[i] > 0 ): # Decrement arr[i] arr[i] - = 1 nleft = left - i if i < = left else K + left - i # Update the maximum # number of groups q = max (q, dfs(arr, nleft, K)) # Increment arr[i] arr[i] + = 1 # Return the value of q return q # Function to find the maximum # number of groups that will # receive fresh donuts def maxGroups(K, arr, n): # Stores count of remainder # by K V = [ 0 for i in range (K)] # Traverse the array arr[] for x in range (n): V[arr[x] % K] + = 1 # Stores maximum number of groups ans = V[ 0 ] + dfs(V, 0 , K) # Return the answer return ans # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) K = 3 print (maxGroups(K, arr, n)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Recursive function to find the // maximum number of groups that // will receive fresh donuts public static int dfs( int [] arr, int left, int K) { // Store the result for the // current state int q = 0; // Check if the leftover donuts // from the previous batch is 0 if (left == 0) { // If true, then one by one // give the fresh donuts // to each group for ( int i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; // Update the maximum // number of groups q = Math.Max(q, 1 + dfs(arr, K - i, K)); // Increment arr[i] arr[i]++; } } } // Otherwise, traverse the given // array, arr[] else { for ( int i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; int nleft = (i <= left ? left - i : K + left - i); // Update the maximum // number of groups q = Math.Max(q, dfs(arr, nleft, K)); // Increment arr[i] arr[i]++; } } } // Return the value of q return q; } // Function to find the maximum // number of groups that will // receive fresh donuts public static int maxGroups( int K, int [] arr) { // Stores count of remainder // by K int [] V = new int [K]; // Traverse the array arr[] foreach ( int x in arr) V[x % K]++; // Stores maximum number of groups int ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } // Driver code public static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5, 6 }; int K = 3; Console.WriteLine(maxGroups(K, arr)); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for the above approach // Recursive function to find the // maximum number of groups that // will receive fresh donuts function dfs(arr, left, K) { // Store the result for the // current state let q = 0; // Check if the leftover donuts // from the previous batch is 0 if (left == 0) { // If true, then one by one // give the fresh donuts // to each group for (let i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; // Update the maximum // number of groups q = Math.max(q, 1 + dfs(arr, K - i, K)); // Increment arr[i] arr[i]++; } } } // Otherwise, traverse the given // array, arr[] else { for (let i = 1; i < K; ++i) { if (arr[i] > 0) { // Decrement arr[i] arr[i]--; let nleft = (i <= left ? left - i : K + left - i); // Update the maximum // number of groups q = Math.max(q, dfs(arr, nleft, K)); // Increment arr[i] arr[i]++; } } } // Return the value of q return q; } // Function to find the maximum // number of groups that will // receive fresh donuts function maxGroups(K, arr, n) { // Stores count of remainder // by K let V = new Array(K).fill(0); // Traverse the array arr[] for (let x = 0; x < n; x++) V[arr[x] % K]++; // Stores maximum number of groups let ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } // Driver Code let arr = [ 1, 2, 3, 4, 5, 6 ]; let n = arr.length; let K = 3; document.write(maxGroups(K, arr, n)) // This code is contributed by _Saurabh_jaiswal </script> |
4
Time Complexity: O(N + KK)
Auxiliary Space: O(K)
Efficient Approach: The above approach has Optimal Substructure and Overlapping Subproblems, therefore, the above approach can also be optimized by memoizing the same recursive calls in a HashMap and use this state when the same problem is called recursively.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the result of the same // recursive calls map<string, int > memo; // Recursive function to find the // maximum number of groups that // will receive fresh donuts int dfs( int V[], int left, int K) { // Store the result for the // current state int q = 0; // Store the key and check // if it is present in the // hashmap string key = "" ; for ( int i = 0; i < K; i++) { key = key + to_string(V[i]); } key += to_string(left); // If already calculated if (memo.find(key) != memo.end()) return memo[key]; // If left is 0 else if (left == 0) { // Traverse the array []arr for ( int i = 1; i < K; ++i) if (V[i] > 0) { // Decrement arr[i] V[i]--; // Update the maximum // number of groups q = max(q, 1 + dfs(V, K - i, K)); // Increment arr[i] by 1 V[i]++; } } // Otherwise, traverse the given // array []arr else { for ( int i = 1; i < K; ++i) { if (V[i] > 0) { // Decrement arr[i] V[i]--; int nleft = i <= left ? left - i : K + left - i; // Update the maximum // number of groups q = max(q, dfs(V, nleft, K)); // Increment arr[i] by 1 V[i]++; } } } // Memoize the result and // return it if (memo.find(key) != memo.end()) memo[key] = q; else memo[key] = q; return q; } // Function to find the maximum // number of groups that will // receive fresh donuts int maxGroups( int K, int arr[]) { // Stores count of remainder by K int V[K]; memset (V, 0, sizeof (V)); // Traverse the array []arr for ( int i = 0; i < 6; i++) V[arr[i] % K]++; // Store the maximum number // of groups int ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int K = 3; cout << maxGroups(K, arr); return 0; } // This code is contributed by divyeshrabadiya07. |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Stores the result of the same // recursive calls static HashMap<String, Integer> memo; // Recursive function to find the // maximum number of groups that // will receive fresh donuts public static int dfs( int [] V, int left, int K) { // Store the result for the // current state int q = 0 ; // Store the key and check // if it is present in the // hashmap String key = Arrays.toString(V); key += Integer.toString(left); // If already calculated if (memo.containsKey(key)) return memo.get(key); // If left is 0 else if (left == 0 ) { // Traverse the array arr[] for ( int i = 1 ; i < K; ++i) if (V[i] > 0 ) { // Decrement arr[i] V[i]--; // Update the maximum // number of groups q = Math.max( q, 1 + dfs(V, K - i, K)); // Increment arr[i] by 1 V[i]++; } } // Otherwise, traverse the given // array arr[] else { for ( int i = 1 ; i < K; ++i) { if (V[i] > 0 ) { // Decrement arr[i] V[i]--; int nleft = i <= left ? left - i : K + left - i; // Update the maximum // number of groups q = Math.max(q, dfs(V, nleft, K)); // Increment arr[i] by 1 V[i]++; } } } // Memoize the result and // return it memo.put(key, q); return q; } // Function to find the maximum // number of groups that will // receive fresh donuts public static int maxGroups( int K, int [] arr) { // Stores count of remainder by K int V[] = new int [K]; // Traverse the array arr[] for ( int x : arr) V[x % K]++; // Hashmap to memoize the results memo = new HashMap<String, Integer>(); // Store the maximum number // of groups int ans = V[ 0 ] + dfs(V, 0 , K); // Return the answer return ans; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 }; int K = 3 ; System.out.println( maxGroups(K, arr)); } } |
Python3
# Python3 program for the above approach # Stores the result of the same # recursive calls memo = {} # Recursive function to find the # maximum number of groups that # will receive fresh donuts def dfs(V, left, K): # Store the result for the # current state q = 0 # Store the key and check # if it is present in the # hashmap v = [ str ( int ) for int in V] key = "," .join(v) key + = str (left) # If already calculated if key in memo: return memo[key] # If left is 0 elif left = = 0 : # Traverse the array []arr for i in range ( 1 , K): if V[i] > 0 : # Decrement arr[i] V[i] - = 1 # Update the maximum # number of groups q = max (q, 1 + dfs(V, K - i, K)) # Increment arr[i] by 1 V[i] + = 1 # Otherwise, traverse the given # array []arr else : for i in range ( 1 , K): if V[i] > 0 : # Decrement arr[i] V[i] - = 1 if i < = left: nleft = left - i else : nleft = K + left - i # Update the maximum # number of groups q = max (q, dfs(V, nleft, K)) # Increment arr[i] by 1 V[i] + = 1 # Memoize the result and # return it if key in memo: memo[key] = q else : memo[key] = q return q # Function to find the maximum # number of groups that will # receive fresh donuts def maxGroups(K, arr): # Stores count of remainder by K V = [ 0 ] * (K) # Traverse the array []arr for x in range ( len (arr)): V[arr[x] % K] + = 1 # Hashmap to memoize the results memo = {} # Store the maximum number # of groups ans = V[ 0 ] + dfs(V, 0 , K) # Return the answer return ans arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] K = 3 print (maxGroups(K, arr)) # This code is contributed by divyesh072019. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Stores the result of the same // recursive calls static Dictionary<String, int > memo; // Recursive function to find the // maximum number of groups that // will receive fresh donuts public static int dfs( int [] V, int left, int K) { // Store the result for the // current state int q = 0; // Store the key and check // if it is present in the // hashmap String key = string .Join( "," , V); key += left.ToString(); // If already calculated if (memo.ContainsKey(key)) return memo[key]; // If left is 0 else if (left == 0) { // Traverse the array []arr for ( int i = 1; i < K; ++i) if (V[i] > 0) { // Decrement arr[i] V[i]--; // Update the maximum // number of groups q = Math.Max( q, 1 + dfs(V, K - i, K)); // Increment arr[i] by 1 V[i]++; } } // Otherwise, traverse the given // array []arr else { for ( int i = 1; i < K; ++i) { if (V[i] > 0) { // Decrement arr[i] V[i]--; int nleft = i <= left ? left - i : K + left - i; // Update the maximum // number of groups q = Math.Max(q, dfs(V, nleft, K)); // Increment arr[i] by 1 V[i]++; } } } // Memoize the result and // return it if (memo.ContainsKey(key)) memo[key] = q; else memo.Add(key, q); return q; } // Function to find the maximum // number of groups that will // receive fresh donuts public static int maxGroups( int K, int [] arr) { // Stores count of remainder by K int []V = new int [K]; // Traverse the array []arr foreach ( int x in arr) V[x % K]++; // Hashmap to memoize the results memo = new Dictionary<String, int >(); // Store the maximum number // of groups int ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 2, 3, 4, 5, 6 }; int K = 3; Console.WriteLine( maxGroups(K, arr)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Stores the result of the same // recursive calls let memo; // Recursive function to find the // maximum number of groups that // will receive fresh donuts function dfs(V, left, K) { // Store the result for the // current state let q = 0; // Store the key and check // if it is present in the // hashmap let key = V.join( "," ); key += left.toString(); // If already calculated if (memo.has(key)) return memo[key]; // If left is 0 else if (left == 0) { // Traverse the array []arr for (let i = 1; i < K; ++i) if (V[i] > 0) { // Decrement arr[i] V[i]--; // Update the maximum // number of groups q = Math.max(q, 1 + dfs(V, K - i, K)); // Increment arr[i] by 1 V[i]++; } } // Otherwise, traverse the given // array []arr else { for (let i = 1; i < K; ++i) { if (V[i] > 0) { // Decrement arr[i] V[i]--; let nleft = i <= left ? left - i : K + left - i; // Update the maximum // number of groups q = Math.max(q, dfs(V, nleft, K)); // Increment arr[i] by 1 V[i]++; } } } // Memoize the result and // return it if (memo.has(key)) memo[key] = q; else memo[key] = q; return q; } // Function to find the maximum // number of groups that will // receive fresh donuts function maxGroups(K, arr) { // Stores count of remainder by K let V = new Array(K); V.fill(0); // Traverse the array []arr for (let x = 0; x < arr.length; x++) V[arr[x] % K]++; // Hashmap to memoize the results memo = new Map(); // Store the maximum number // of groups let ans = V[0] + dfs(V, 0, K); // Return the answer return ans; } let arr = [ 1, 2, 3, 4, 5, 6 ]; let K = 3; document.write(maxGroups(K, arr)); // This code is contributed by rameshtravel07. </script> |
4
Time Complexity: O(N + K2)
Auxiliary Space: O(K)
Contact Us