Distribute the Maximum Number of Chocolates Amongst X Students

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

Run Code

Time Complexity

The time complexity of the naive approach is O(n²) 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

Run Code

Time Complexity

The time complexity of the naive approach is O(n²) 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.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is the hashing method in C++?

Hashing is mapping an abstract data type to an integer and then storing the integer as a key to access the abstract datatype.

What is the time complexity of the Naive Approach?

The time complexity of the naive approach is O(n²) as it consists of two loops.

What is the space complexity of the Naive Approach?

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

What is the time complexity of the Optimal Approach?

The time complexity of the optimal approach is O(n) as we are using one loop for iteration.

What is the space complexity of the Optimal Approach?

The space complexity of the optimal approach is O(n) as we require any extra array sum_choco for computing the result.

Conclusion

In this article, we have extensively discussed the problem of distributing the maximum number of chocolates amongst X students.

Recommended Problems -

• Flattening A Linked List
• Sorted Doubly Linked List
• Linked List Cycle ii
   

To give an edge to your coding preparation, you can refer to our blog Clone a binary tree with random pointers, and Flattening a Multi-level Linked List(Depth Wise). You can also refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, React, JavaScript, System Design, etc. 

Happy Learning!