Formatted question description: https://leetcode.ca/all/1760.html

# 1760. Minimum Limit of Balls in a Bag

## Level

Medium

## Description

You are given an integer array `nums`

where the `i-th`

bag contains nums[i] balls. You are also given an integer `maxOperations`

.

You can perform the following operation at most `maxOperations`

times:

- Take any bag of balls and divide it into two new bags with a
**positive**number of balls. /* For example, a bag of`5`

balls can become two new bags of`1`

and`4`

balls, or two new bags of`2`

and`3`

balls.

Your penalty is the **maximum** number of balls in a bag. You want to **minimize** your penalty after the operations.

Return *the minimum possible penalty after performing the operations*.

**Example 1:**

**Input:** nums = [9], maxOperations = 2

**Output:** 3

**Explanation: **

- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].

The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

**Example 2:**

**Input:** nums = [2,4,8,2], maxOperations = 4

**Output:** 2

**Explanation:**

- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].

The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

**Example 3:**

**Input:** nums = [7,17], maxOperations = 2

**Output:** 7

**Constraints:**

`1 <= nums.length <= 10^5`

`1 <= maxOperations, nums[i] <= 10^9`

## Solution

Sort the array `nums`

. Use binary search, where initially let `low = 1`

and `high = nums[nums.length - 1]`

. Each time let `mid`

be the mean of `low`

and `high`

, and calculate whether `penalty = mid`

is possible. Find the minimum possible `penalty`

during binary search, and finally return the minimum possible `penalty`

.

```
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
Arrays.sort(nums);
int length = nums.length;
int low = 1, high = nums[length - 1];
while (low < high) {
int mid = (high - low) / 2 + low;
if (isPossible(nums, maxOperations, mid))
high = mid;
else
low = mid + 1;
}
return low;
}
public boolean isPossible(int[] nums, int maxOperations, int penalty) {
int count = 0;
for (int i = nums.length - 1; i >= 0; i--) {
int num = nums[i];
if (num <= penalty)
break;
int operations = nums[i] / penalty - 1;
if (nums[i] % penalty != 0)
operations++;
count += operations;
}
return count <= maxOperations;
}
}
```