Boxes Of Chocolates
This is the time when Dr. Stephen wants to distribute chocolates. He has N number of boxes in a row, and each box contains some chocolates. Now, He wants to distribute chocolates to K children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, he decided to give the maximum number of chocolates equally to K children.

Formally, There are N boxes with a different number of chocolates in them. The task is to divide the chocolates equally among K children where you can only choose consecutive boxes(subarray) to distribute chocolates. You need to print the maximum number of chocolates each child can get.

For Example: for the given boxes of chocolates [3,2,2,5,4,1] and 5 students.

Output: 2 If there is no restriction on choosing the boxes then the maximum number of chocolates the 5 students equally can have is 3 by picking all boxes except the box at index 2(0-based indexing). So total candies will be 3+2+5+4+1 = 15 and each of the 5 students will get 15/5=3 candies. But we are allowed to choose only consecutive boxes. So if we choose boxes [0,1] then 3+2=5 then each student will have only 1 chocolate and when we choose boxes[4,6] as 5+4+1=10 then each student will have 2 chocolates. So the maximum number of chocolates each student can get is 2.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains two single space-separated integers N, and K, denoting the total number of boxes and the total number of students respectively. The second line of each test case contains 'N' single space-separated integers representing the count of chocolates in each of the N boxes.

Output Format:

For each test case, print an integer denoting the maximum number of chocolates each child can get in a single line

Constraints:

1

Question

Boxes Of Chocolates

This is the time when Dr. Stephen wants to distribute chocolates. He has N number of boxes in a row, and each box contains some chocolates. Now, He wants to distribute chocolates to K children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, he decided to give the maximum number of chocolates equally to K children.

Formally, There are N boxes with a different number of chocolates in them. The task is to divide the chocolates equally among K children where you can only choose consecutive boxes(subarray) to distribute chocolates. You need to print the maximum number of chocolates each child can get.

For Example: for the given boxes of chocolates [3,2,2,5,4,1] and 5 students.

Output: 2 

If there is no restriction on choosing the boxes then the maximum number of chocolates the 5 students equally can have is 3 by picking all boxes except the box at index 2(0-based indexing). So total candies will be 3+2+5+4+1 = 15 and each of the 5 students will get 15/5=3 candies. 

But we are allowed to choose only consecutive boxes. So if we choose boxes [0,1] then 3+2=5 then each student will have only 1 chocolate and when we choose boxes[4,6] as 5+4+1=10 then each student will have 2 chocolates. So the maximum number of chocolates each student can get is 2.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow. 

The first line of each test case contains two single space-separated integers N, and K, denoting the total number of boxes and the total number of students respectively.

The second line of each test case contains 'N' single space-separated integers representing the count of chocolates in each of the N boxes.

Output Format:

For each test case, print an integer denoting the maximum number of chocolates each child can get in a single line

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 10^5
0 <= boxes[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Step 1- Sorted the array.
Step 2 - applied two pointer approach i.e took two integers i and j, point i to first element while pointing j to the last element of the array.
Step 3 - in every step do count++ and j--;
Step 4 - if sum of ith and jth element is less than K then do i++;

Accepted Answer

Brute Force

The naive solution is to check whether each subarray sum is divisible by K or not. And then find the maximum of the sum/K from all subarray sum.
To find the subarray we will run two loops in which the outer loop will traverse each element of the array and the inner loop will increment our current sum with arr[j] then check if the current sum is divisible by K or not and update the max if the current sum is divisible by K.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, only a constant space is required.

Time Complexity: O(1)Explanation:

O(N^2), where ‘N’ is the total number of boxes.

In the worst case, for each element in the array (O(N)), we will be checking the subarray of N elements(O(N)) in the worst case. Thus a total of O(N^2) time will be required.

Accepted Answer

Hash Map

The better idea is to create the sum array in which sum[i] stores the sum from (arr[0]....+arr[i]) and a hash table storing remainder as key and values as an index which represents the first index in the array where sum[i]%K i.e that remainder found.

Now to find the maximum subarray sum which divides K.
We will start traversing from index 0 to N-1 at each index we find the sum[i]%K and store in the currentRemainder variable.
1. If currentRemainder = 0 then it means sum from arr[0] to arr[i] is divisible by K and we will update our maxSum.
2. Else we check if currentRemainder is present in a hashtable or not.
  1. If Hashtable does not contain then we insert currentRemainder in the hashtable with key, value as (currentRemaider, i).
  2. Else we get the value associate with currentRemainder from HashTable to say prevIndex which have the same remainder found previously and if we remove the sum from 0 to prevIndex from the sum[i] i.e sum[i]-sum[prevIndex] is a sum which is divisible by K. and we update maxSum
Finally, return (maxSum / K).

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the total number of boxes.

In the worst case, we will be storing the prefix sums in an array, of size N, and create a Map that can contain N remainders in the worst time. Thus a total of O(N) space will be required.