Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Naive Approach
3.1.
Method
3.2.
Code
3.3.
Time Complexity
3.4.
Space Complexity
4.
Optimal Approach
4.1.
Method
4.2.
Code
4.3.
Time Complexity
4.4.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is the hashing method in C++?
5.2.
What is the time complexity of the Naive Approach?
5.3.
What is the space complexity of the Naive Approach?
5.4.
What is the time complexity of the Optimal Approach?
5.5.
What is the space complexity of the Optimal Approach?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Distribute the Maximum Number of Chocolates Amongst X Students

Author Lucifer go
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Time Complexity

The time complexity of the naive approach is O(n2) 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;
}

Time Complexity

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

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!

Previous article
Distribute items such that a person cannot take more than two items of the same type
Next article
Difference between highest and least frequencies in an array
Live masterclass