# 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[0]+..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[0]+..+arr[i]) and sum[j] = sum(arr[0]+..+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 um;        // 'sum[]' to store cumulative sum, where     // sum[i] = sum(arr[0]+..arr[i])     int sum[n], 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.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[0]);     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[0]+..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[0]+..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 um =                      new Dictionary();                // 'sum[]' to store cumulative          // sum, where sum[i] =          // sum(arr[0]+..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.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).

## tags:

Arrays Hash Amazon Amazon Arrays Hash