# Minimum count of balls in a bag

Posted: 10 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### After performing the operations, let ‘X’ be the maximum number of balls in a bag. The task is to find the minimum possible value of ‘X’ and return it.

##### Example:
``````ARR = [5, 7], N = 2, M = 2

Perform the following two operations on ‘ARR’:
1. Divide the bag with 7 balls into 3 and 4. New ARR = [3, 4, 5].
2. Divide the bag with 5 balls into 1 and 4. New ARR = [1, 3, 4, 4].

The bag with the maximum number of balls has 4 balls. Hence, the minimum possible value of ‘X’ is 4. Return 4 as the answer.
``````
##### Note:
``````1. You can perform any number of operations between [0, M], both included.
2. Avoid using the 'Modulo' operator as it can cause Time Limit Exceeded.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the size of array ‘ARR’ and the maximum number of operations.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.
``````
##### Output format:
``````For every test case, return the minimum possible value of ‘X’.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N, M <= 10^3
1 <= ARR[i] <= 10^6

Time limit: 1 sec
``````