Minimum Count of Balls in a Bag Problem Statement
You are given an integer array ARR
of size N
, where ARR[i]
represents the number of balls in the i-th
bag. Additionally, you have an integer M
, which indicates the maximum number of operations you can perform on this collection of bags.
Explanation:
In each operation, you have the option to choose a bag from the collection and split it into two new bags in such a way that each bag contains a positive number of balls. The original bag is then removed from the collection, and the new bags are added.
Your task is to determine the minimum possible value of X
, where X
is the maximum number of balls in a bag after performing the operations, and return this value.
Input:
The first line of input contains an integer ‘T’ indicating the number of test cases. For each test case, the following inputs are given:
- First line: Two space-separated integers ‘N’ and ‘M’, the size of the array ‘ARR’ and the maximum number of operations.
- Second line: ‘N’ space-separated integers representing the elements of the array ‘ARR’.
Output:
For each test case, return the minimum possible value of ‘X’.
Example:
Input:
ARR = [5, 7], N = 2, M = 2
Operations:
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 maximum number of balls in a bag is 4. Therefore, the minimum possible value of ‘X’ is 4. Return 4 as the result.
Constraints:
- 1 <= T <= 10
- 1 <= N, M <= 103
- 1 <= ARR[i] <= 106
- Time limit: 1 sec
Note:
1. You can perform any number of operations between [0, M], both inclusive.
2. Avoid using the 'Modulo' operator as it can lead to exceeding time limits.
Find the minimum possible value of the maximum number of balls in a bag after performing a given number of operations.
Iterate through the bags and split them to minimize the maximum number of balls.
Ke...read more
Top HashedIn by Deloitte SDE-2 interview questions & answers
Popular interview questions of SDE-2
Top HR questions asked in HashedIn by Deloitte SDE-2
Reviews
Interviews
Salaries
Users/Month