“The maximum number of chocolates to be distributed equally among k students” states that you are given n boxes that have some chocolates in it. Suppose there are k students. The task is to distribute the maximum number of chocolates among k students equally, by selecting consecutive boxes. We can assume that boxes are in a row consisting of numbers from 1 to n. the task is to select a group of boxes that can distribute the most number of chocolates to k students equally. The boxes which are given can be considered as an array and arr[i] can represent the number of chocolates in it at the position of i’th index.
Table of Contents
Example
arr[] = {1, 5, 3, 6, 10, 1}
k = 38
Explanation: The numbers from sub-array 5, 3, 6, 10 constitute 24 chocolates which can be distributed among k students. That means 8 chocolates per student, which is the maximum of given values.
Algorithm
1. Declare a map.
2. Declare an array ‘sum’ of size n (length of the given array).
3. Set resultant to 0 and copy the value of arr[0] to sum[0].
4. Add all the values of arr[i] and sum[i-1] and store each value at sum[i].
5. Traverse the array, while i < n (length of the array).
1. Set temp to sum[i]%k and check if the temp is equal to 0.
1. If true then check for if resultant is less than sum[i], if true, then update resultant = sum[i].
2. Check if the temp is present in a map, if present, then, push this value and the current index into the map.
3. Else get the number which is related with the temp in a map, let x= map[temp], check if resultant is less than the sum[i] –sum[x].
1. If true then update the value of resultant=sum[i]-sum[x], where x is map[temp].
6. Return the (resultant / k ).Explanation
We have given a task to distribute the maximum chocolates equally among k students. The box is basically an array representing the number of chocolates. One condition is also there, we must choose consecutive boxes to disttribute chocolates and distribution should be maximized.
We are going to use hashing. We will declare a Map. But, before that we will be creating an empty array, of the same size as of given array, that is n. Set the value sum[0] as of arr[0], means the first value of sum[0] should be same as arr[0]. While traversing the array, we will be adding the arr[i] and sum[i-1] and store the value into sum[i], in this manner, we will be adding up the values of an array and sum’s previous indexes element. We will have the values in it sum array.
Let us take an example of it:
Example
arr[]={1, 5, 3, 6, 10, 1}, k=3
sum[0]=arr[0]=1.
sum[1]=arr[i]+sum[i-1]=6,
sum[2]=arr[i]+sum[i-1]=9, continuing it, we will have the following values in sum array.
sum[]={1, 6, 9, 15, 25, 26}.
We will traverse the array again, picking up temp as sum [i] % k. We will check for if the temp is equal to 0, but it is not, so we will check for if the map doesn’t contain this value, we will be putting it with the current index in a map. So on the map, we have (1,0) now.
Picking up the next number 6 and checking sum[i] % k as a temp, is found to be 0 now, so we will update the resultant now. Resultant would be 6.
The next element would be 9 and 15, in this pattern both have modulo to 3 is 0, so up to 15, the resultant would be 15. The next number is 25, we have a temp now like 1. So we will jump on to the else condition. But we have 1 already into the map. So we will get the value of it and that is 0, as we stored 1 and 0 into the map. Then we will find out the sum[i]-sum[0], and that will be 24, update resultant to this number.
After visiting one more number, we still have the answer as it is 24. Finally, we will return 24/3 that is 8. This will be our final answer.
Implementation
C++ program for Maximum number of chocolates to be distributed equally among k students
#include<iostream>
#include<unordered_map>
using namespace std;
int getChocolateNumbers(int arr[], int n, int k)
{
unordered_map<int, int> MAP;
int sum[n];
int resultant = 0;
sum[0] = arr[0];
for (int i = 1; i < n; i++)
sum[i] = sum[i - 1] + arr[i];
for (int i = 0; i < n; i++)
{
int temp = sum[i] % k;
if (temp == 0)
{
if (resultant < sum[i])
resultant = sum[i];
}
else if (MAP.find(temp) == MAP.end())
MAP[temp] = i;
else if (resultant < (sum[i] - sum[MAP[temp]]))
resultant = sum[i] - sum[MAP[temp]];
}
return (resultant / k);
}
int main()
{
int arr[] = {1, 5, 3, 6, 10, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Number of chocolates which can be equally distributed: "<< getChocolateNumbers(arr, n, k);
return 0;
}
Number of chocolates which can be equally distributed: 8
Java program for Maximum Number of Chocolates to be Distributed Equally Among k Students
import java.util.HashMap;
class distributionOfChocolates
{
public static int getChocolateNumbers(int arr[], int n, int k)
{
HashMap <Integer,Integer> MAP = new HashMap<Integer,Integer>();
int sum[]=new int[n];
int resultant = 0;
sum[0] = arr[0];
for (int i = 1; i < n; i++)
{
sum[i] = sum[i - 1] + arr[i];
}
for (int i = 0; i < n; i++)
{
int temp = sum[i] % k;
if (temp == 0)
{
if (resultant < sum[i])
resultant = sum[i];
}
else if (!MAP.containsKey(temp) )
MAP.put(temp, i);
else if (resultant < (sum[i] - sum[MAP.get(temp)]))
resultant = sum[i] - sum[MAP.get(temp)];
}
return (resultant / k);
}
public static void main(String[] args)
{
int arr[] = { 1,5,3,6,10,1 };
int n = arr.length;
int k = 3;
System.out.println("Number of chocolates which can be equally distributed: "+ getChocolateNumbers(arr, n, k));
}
}
Number of chocolates which can be equally distributed: 8
Complexity Analysis for Maximum Number of Chocolates to be Distributed Equally Among k Students
Time Complexity
O(n) where “n” is the number of elements in the array.
Space Complexity
O(n) where “n” is the number of elements in the array.