# Maximum number of chocolates to be distributed equally among k students

Given n boxes containing some chocolates arranged in a row. There are k number of students. The problem is to distribute maximum number of chocolates equally among k students by selecting a consecutive sequence of boxes from the given lot. Consider the boxes are arranged in a row with numbers from 1 to n from left to right. We have to select a group of boxes which are in consecutive order that could provide maximum number of chocolates equally to all the k students. An array arr[] is given representing the row arrangement of the boxes and arr[i] represents number of chocolates in that box at position ‘i’.

Examples:

```Input : arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Output : 6
The subarray is {7, 6, 1, 4} with sum 18.
Equal distribution of 18 chocolates among
3 students is 6.
Note that the selected boxes are in consecutive order
with indexes {1, 2, 3, 4}.
```

Source: Asked in Amazon.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The problem is to find maximum sum sub-array divisible by k and then return (sum / k).

Method 1 (Naive Approach): Consider the sum of all the sub-arrays. Select the maximum sum. Let it be maxSum. Return (maxSum / k). Time Complexity is of O(n2).

Method 2 (Efficient Approach): Create an array sum[] where sum[i] stores sum(arr+..arr[i]). Create a hash table having tuple as (ele, idx), where ele represents an element of (sum[i] % k) and idx represents the element’s index of first occurrence when array sum[] is being traversed from left to right. Now traverse sum[] from i = 0 to n and follow the steps given below.

1. Calculate current remainder as curr_rem = sum[i] % k.
2. If curr_rem == 0, then check if maxSum < sum[i], update maxSum = sum[i].
3. Else if curr_rem is not present in the hash table, then create tuple (curr_rem, i) in the hash table.
4. Else, get the value associated with curr_rem in the hash table. Let this be idx. Now, if maxSum < (sum[i] – sum[idx]) then update maxSum = sum[i] – sum[idx].

Finally, return (maxSum / k).

Explanation:
If (sum[i] % k) == (sum[j] % k), where sum[i] = sum(arr+..+arr[i]) and sum[j] = sum(arr+..+arr[j]) and ‘i’ is less than ‘j’, then sum(arr[i+1]+..+arr[j]) must be divisible by ‘k’.

## C++

 `// C++ implementation to find the maximum number ` `// of chocolates to be distributed equally among ` `// k students ` `#include ` `using` `namespace` `std; ` ` `  `// function to find the maximum number of chocolates ` `// to be distributed equally among k students ` `int` `maxNumOfChocolates(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// unordered_map 'um' implemented as ` `    ``// hash table ` `    ``unordered_map<``int``, ``int``> um; ` ` `  `    ``// 'sum[]' to store cumulative sum, where ` `    ``// sum[i] = sum(arr+..arr[i]) ` `    ``int` `sum[n], curr_rem; ` ` `  `    ``// to store sum of sub-array having maximum sum ` `    ``int` `maxSum = 0; ` ` `  `    ``// building up 'sum[]' ` `    ``sum = arr; ` `    ``for` `(``int` `i = 1; i < n; i++) ` `        ``sum[i] = sum[i - 1] + arr[i]; ` ` `  `    ``// traversing 'sum[]' ` `    ``for` `(``int` `i = 0; i < n; i++) { ` ` `  `        ``// finding current remainder ` `        ``curr_rem = sum[i] % k; ` ` `  `        ``// if true then sum(0..i) is divisible ` `        ``// by k ` `        ``if` `(curr_rem == 0) { ` `            ``// update 'maxSum' ` `            ``if` `(maxSum < sum[i]) ` `                ``maxSum = sum[i]; ` `        ``} ` ` `  `        ``// if value 'curr_rem' not present in 'um' ` `        ``// then store it in 'um' with index of its ` `        ``// first occurrence ` `        ``else` `if` `(um.find(curr_rem) == um.end()) ` `            ``um[curr_rem] = i; ` ` `  `        ``else` `            ``// if true, then update 'max' ` `            ``if` `(maxSum < (sum[i] - sum[um[curr_rem]])) ` `            ``maxSum = sum[i] - sum[um[curr_rem]]; ` `    ``} ` ` `  `    ``// required maximum number of chocolates to be ` `    ``// distributed equally among 'k' students ` `    ``return` `(maxSum / k); ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = { 2, 7, 6, 1, 4, 5 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``int` `k = 3; ` `    ``cout << ``"Maximum number of chocolates: "` `         ``<< maxNumOfChocolates(arr, n, k); ` `    ``return` `0; ` `} `

## Java

 `// Java implementation to find the maximum number ` `// of chocolates to be distributed equally among ` `// k students ` `import` `java.io.*; ` `import` `java.util.*; ` `class` `GFG { ` `// Function to find the maximum number of chocolates ` `// to be distributed equally among k students ` `static` `int` `maxNumOfChocolates(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// Hash table ` `    ``HashMap um = ``new` `HashMap(); ` ` `  `    ``// 'sum[]' to store cumulative sum, where ` `    ``// sum[i] = sum(arr+..arr[i]) ` `    ``int``[] sum=``new` `int``[n]; ` `    ``int` `curr_rem; ` ` `  `    ``// To store sum of sub-array having maximum sum ` `    ``int` `maxSum = ``0``; ` ` `  `    ``// Building up 'sum[]' ` `    ``sum[``0``] = arr[``0``]; ` `    ``for` `(``int` `i = ``1``; i < n; i++) ` `        ``sum[i] = sum[i - ``1``] + arr[i]; ` ` `  `    ``// Traversing 'sum[]' ` `    ``for` `(``int` `i = ``0``; i < n; i++) { ` ` `  `        ``// Finding current remainder ` `        ``curr_rem = sum[i] % k; ` ` `  `        ``// If true then sum(0..i) is divisible ` `        ``// by k ` `        ``if` `(curr_rem == ``0``) { ` `            ``// update 'maxSum' ` `            ``if` `(maxSum < sum[i]) ` `                ``maxSum = sum[i]; ` `        ``} ` ` `  `        ``// If value 'curr_rem' not present in 'um' ` `        ``// then store it in 'um' with index of its ` `        ``// first occurrence ` `        ``else` `if` `(!um.containsKey(curr_rem) ) ` `            ``um.put(curr_rem , i); ` ` `  `        ``else` `            ``// If true, then update 'max' ` `            ``if` `(maxSum < (sum[i] - sum[um.get(curr_rem)])) ` `            ``maxSum = sum[i] - sum[um.get(curr_rem)]; ` `    ``} ` ` `  `    ``// Required maximum number of chocolates to be ` `    ``// distributed equally among 'k' students ` `    ``return` `(maxSum / k); ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String[] args) ` `{ ` `int` `arr[] = { ``2``, ``7``, ``6``, ``1``, ``4``, ``5` `}; ` `int` `n = arr.length; ` `int` `k = ``3``; ` `System.out.println(``"Maximum number of chocolates: "` `                    ``+ maxNumOfChocolates(arr, n, k)); ` `} ` `    ``} ` ` `  `// This code is contributed by 'Gitanjali'. `

## Python3

 `# Python3 implementation to  ` `# find the maximum number ` `# of chocolates to be  ` `# distributed equally ` `# among k students ` ` `  `# function to find the ` `# maximum number of chocolates ` `# to be distributed equally ` `# among k students ` `def` `maxNumOfChocolates(arr, n, k): ` `     `  `    ``um, curr_rem, maxSum ``=` `{}, ``0``, ``0` `     `  `    ``# 'sm[]' to store cumulative sm, ` `    ``# where sm[i] = sm(arr+..arr[i]) ` `    ``sm ``=` `[``0``]``*``n ` `    ``sm[``0``] ``=` `arr[``0``] ` `     `  `    ``# building up 'sm[]' ` `    ``for` `i ``in` `range``(``1``, n): ` `        ``sm[i] ``=` `sm[i ``-` `1``] ``+` `arr[i] ` `         `  `    ``# traversing 'sm[]' ` `    ``for` `i ``in` `range``(n): ` ` `  `        ``# finding current remainder ` `        ``curr_rem ``=` `sm[i] ``%` `k ` `         `  `        ``if` `(``not` `curr_rem ``and` `maxSum < sm[i]) :  ` `            ``maxSum ``=` `sm[i] ` `        ``elif` `(``not` `curr_rem ``in` `um) : ` `            ``um[curr_rem] ``=` `i ` `        ``elif` `(maxSum < (sm[i] ``-` `sm[um[curr_rem]])): ` `              ``maxSum ``=` `sm[i] ``-` `sm[um[curr_rem]] ` `         `  `    ``return` `maxSum``/``/``k ` `     `  `# Driver program to test above ` `arr ``=` `[ ``2``, ``7``, ``6``, ``1``, ``4``, ``5` `] ` `n, k ``=` `len``(arr), ``3` ` `  `print``(``"Maximum number of chocolates: "` `+` `     ``str``(maxNumOfChocolates(arr, n, k))) ` ` `  `# This code is contributed by Ansu Kumari `

## C#

 `// C# implementation to find  ` `// the maximum number of  ` `// chocolates to be distributed  ` `// equally among k students ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{ ` `    ``// Function to find the  ` `    ``// maximum number of  ` `    ``// chocolates to be distributed  ` `    ``// equally among k students ` `    ``static` `int` `maxNumOfChocolates(``int` `[]arr,  ` `                                  ``int` `n, ``int` `k) ` `    ``{ ` `        ``// Hash table ` `        ``Dictionary <``int``, ``int``> um =  ` `                    ``new` `Dictionary<``int``, ``int``>(); ` `     `  `        ``// 'sum[]' to store cumulative  ` `        ``// sum, where sum[i] =  ` `        ``// sum(arr+..arr[i]) ` `        ``int``[] sum = ``new` `int``[n]; ` `        ``int` `curr_rem; ` `     `  `        ``// To store sum of sub-array ` `        ``// having maximum sum ` `        ``int` `maxSum = 0; ` `     `  `        ``// Building up 'sum[]' ` `        ``sum = arr; ` `        ``for` `(``int` `i = 1; i < n; i++) ` `            ``sum[i] = sum[i - 1] + arr[i]; ` `     `  `        ``// Traversing 'sum[]' ` `        ``for` `(``int` `i = 0; i < n; i++)  ` `        ``{ ` `     `  `            ``// Finding current ` `            ``// remainder ` `            ``curr_rem = sum[i] % k; ` `     `  `            ``// If true then sum(0..i)  ` `            ``// is divisible by k ` `            ``if` `(curr_rem == 0)  ` `            ``{ ` `                ``// update 'maxSum' ` `                ``if` `(maxSum < sum[i]) ` `                    ``maxSum = sum[i]; ` `            ``} ` `     `  `            ``// If value 'curr_rem' not ` `            ``// present in 'um' then store ` `            ``// it in 'um' with index of  ` `            ``// its first occurrence ` `            ``else` `if` `(!um.ContainsKey(curr_rem)) ` `                ``um.Add(curr_rem , i); ` `     `  `            ``else` `             `  `                ``// If true, then ` `                ``// update 'max' ` `                ``if` `(maxSum < (sum[i] -  ` `                    ``sum[um[curr_rem]])) ` `                ``maxSum = sum[i] -  ` `                         ``sum[um[curr_rem]]; ` `        ``} ` `     `  `        ``// Required maximum number  ` `        ``// of chocolates to be  ` `        ``// distributed equally ` `        ``// among 'k' students ` `        ``return` `(maxSum / k); ` `    ``} ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `    ``int` `[]arr = ``new` `int``[]{ 2, 7, 6, 1, 4, 5 }; ` `    ``int` `n = arr.Length; ` `    ``int` `k = 3; ` `    ``Console.Write(``"Maximum number of chocolates: "` `+  ` `                     ``maxNumOfChocolates(arr, n, k)); ` `    ``} ` `} ` ` `  `// This code is contributed by ` `// Manish Shaw(manishshaw1) `

Output :

```Maximum number of chocolates: 6
```

Time Complexity: O(n).
Auxiliary Space: O(n).

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Hash Amazon Amazon Arrays Hash

code

load comments