In this blog, we will discuss how to implement an algorithm for solving the problem of distributing the maximum number of chocolates amongst X students in an optimal manner.

We would be looking at the algorithms for the brute force approach as well as the optimal approach and will code both the approaches in C++ for reference.

Problem Statement

You are given n boxes with some chocolates arranged in a row. Then, there is a k number of students. The problem is distributing the maximum number of chocolates equally among k students by selecting a consecutive sequence of boxes from the given array of boxes.

Consider that the boxes are arranged in a row numbered 1 to n from left to right. The objective is to select boxes in consecutive order that could provide the maximum number of chocolates equally to all the k students. An array of chocolates[] is given, representing the row arrangement of the boxes containing chocolates, and chocolates[i] represent the number of chocolates in that box at position 'i'.

For example: -

Input : arr[] = {2, 7, 6, 1, 4, 2}, k = 3

Output : 6

Consider the subarray with {7, 6, 1, 4} as consecutive contents and thus sum = 18. The equal distribution of 18 chocolates among 3 students is 6.

Naive Approach

Method

The naive approach considers the sum of all the sub-arrays and then selects the maximum sum. Let it be max_sum. Return (max_sum / k) where k is the number of students.

We take an integer array of chocolates[] representing the number of chocolate in consecutive containers.

The number of boxes is represented by â€˜n.â€™

The number of students is represented by â€˜k.â€™

The function max_chocolate( int chocolate[], int n, int k ) takes three arguments âˆ’ the array, size, and no. of students k.

We will start traversing the chocolate[] from the beginning using for loop.

Take two variables, sum and max_sum. The variable sum stores the sum of consecutive elements of the subarray.

max_sum is used to store the maximum sum found so far.

Inside nested for loop, keep adding the elements and check if sum%k gives remainder 0.

Also if this sum > max_sum, update max_sum.

At last, return the result as max_sum/k, which is the number of chocolates each student gets.

Code

#include <bits/stdc++.h>
int max_chocolates(int chocolates[], int n, int k){
int sum;
int max_sum = 0;
for(int i=0;i<n;i++){
sum=0;
for(int j=i;j<n;j++){
sum+=chocolates[j];
if(sum%k==0 && sum>max_sum)
max_sum=sum; //updating the maximum sum
}
}
return (max_sum / k);
}
int main(){
int chocolates[] = { 2, 7, 6, 1, 4, 5 };
int n = 6;
int k =3;
printf("Maximum number of chocolates to be distributed equally among k students: %d ",max_chocolates(chocolates, n, k));
return 0;
}

You can also try this code with Online C++ Compiler

The time complexity of the naive approach is O(n^{2}) as it consists of two loops.

Space Complexity

The space complexity of the naive approach is O(1) as we don't require any extra space for computing the result.

Optimal Approach

Method

Create an array sum_choco[] where sum_choco[i] stores sum of number of chocolates from index 0 to index i.

Create a hash table with a tuple (ele, idx), where ele represents values of (sum[i] % k), and idx represents the index of the first occurrence of the element when the array sum_choco[] is being traversed from left to right.

Traverse sum_choco[] from indexes 0 to n and calculate as below.

Calculate current remainder as remainder = sum_choco[i] % k.

If remainder == 0, then check if max_sum < sum_choco[i], update max_sum = sum_choco[i].

Else if the remainder is not present in the hash table, then create a tuple (remainder, i) in the hash table.

Else, get the value associated with remainder in the table. Let this be idx. Now, if max-sum < (sum[i] â€“ sum[idx]) then update max_sum = sum[i] â€“ sum[idx].

Finally, return (max_sum / k).

Explanation: If (sum_choco[i] % k) == (sum_choco[j] % k), where sum_choco[i] = sum(arr[0]+..+arr[i]) and sum_choco[j] = sum(arr[0]+..+arr[j]) and â€˜iâ€™ is less than â€˜jâ€™, then sum(arr[i+1]+..+arr[j]) must be divisible by â€˜kâ€™.

Code

#include <bits/stdc++.h>
using namespace std;
int max_chocolates(int chocolates[], int n, int k)
{
// unordered_map 'map' implemented as
// hash table
unordered_map<int, int> map;
// 'sum_choco[]' to store cumulative sum_choco, where
// sum_choco[i] = sum_choco(chocolates[0]+..chocolates[i])
int sum_choco[n], curr_remainder;
// to store sum_choco of sub-array having maximum sum_choco
int max_sum = 0;
// building up 'sum_choco[]'
sum_choco[0] = chocolates[0];
for (int i = 1; i < n; i++)
sum_choco[i] = sum_choco[i - 1] + chocolates[i];
// traversing 'sum_choco[]'
for (int i = 0; i < n; i++) {
// finding current curr_remainder
curr_remainder = sum_choco[i] % k;
// if true then sum_choco(0..i) is divisible by k
if (curr_remainder == 0) {
// update 'max_sum'
if (max_sum < sum_choco[i])
max_sum = sum_choco[i];
}
// if value 'curr_remainder' not present in 'map' then store it in 'map' with index of its
// first occurrence
else if (map.find(curr_remainder) == map.end())
map[curr_remainder] = i;
else
// if true, then update 'max'
if (max_sum < (sum_choco[i] - sum_choco[map[curr_remainder]]))
max_sum = sum_choco[i] - sum_choco[map[curr_remainder]];
}
// required maximum number of chocolates to be
// distributed equally among 'k' students
return (max_sum / k);
}
int main()
{
int chocolates[] = { 2, 7, 6, 1, 4, 5 };
int n = 6;
int k = 3;
cout << "Maximum number of chocolates to be distributed equally among k students: "<< max_chocolates(chocolates, n, k);
return 0;
}

You can also try this code with Online C++ Compiler