Last Updated: 14 Oct, 2020
##### Boxes Of Chocolates
Moderate
Problem statement

#### 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
``````
Approaches

## 01Approach

• 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.