# Minimum Limit of Balls in a Bag
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag)
Canonical: https://scaleengineer.com/dsa/problems/minimum-limit-of-balls-in-a-bag
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit)
---
## Problem
You are given an integer array `nums` where the `ith` 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, and you should return 2.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= maxOperations, nums[i] <= 109`

# Approaches
## Greedy Approach with Max-Heap
This approach uses a greedy strategy. At each step, we have one operation to perform. To minimize the overall penalty (the maximum number of balls in any bag), it is always optimal to operate on the bag that currently contributes the most to this maximum. We can use a max-heap to efficiently track and select the bag that, when split, provides the greatest reduction in penalty. The heap will store the state of each original bag, ordered by the current size of its pieces.
**Time:** O((N + K) * log N), where N is the number of bags and K is `maxOperations`. Initializing the heap takes O(N log N). Each of the K operations involves a heap pop and push, taking O(log N) time. · **Space:** O(N), where N is the number of bags, to store the elements in the max-heap.
**Pros:** It's a conceptually straightforward greedy approach.; It correctly solves the problem if it runs to completion.
**Cons:** The time complexity is proportional to `maxOperations`. Since `maxOperations` can be as large as 10^9, this approach is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on many test cases.
### Explanation
We can model the problem as follows: for each original bag, we can spend operations to split it into more and more pieces. If an original bag of size `s` is split into `k` pieces, it takes `k-1` operations, and the new maximum size of these pieces is `ceil(s/k)`. The greedy choice is to always spend one operation on the set of pieces that currently has the highest value.

We use a max-heap to keep track of the current penalty for each original bag. The heap will store tuples or objects containing `(current_penalty, original_size, num_pieces)`. The heap is ordered by `current_penalty`.

The algorithm is as follows:
1. Initialize a max-heap. For each number `num` in the input array `nums`, push a tuple `(num, num, 1)` into the heap. This represents that initially, each bag is 1 piece of its original size.
2. Loop for `maxOperations` times:
    a. Extract the element with the maximum penalty from the heap. Let this be `(penalty, original_size, num_pieces)`.
    b. We "use" one operation on this original bag. Increment the number of pieces: `num_pieces_new = num_pieces + 1`.
    c. Calculate the new penalty for this bag: `penalty_new = ceil(original_size / num_pieces_new)`.
    d. Insert the new state `(penalty_new, original_size, num_pieces_new)` back into the heap.
3. After the loop finishes, the top element of the heap contains the maximum penalty in the first element of its tuple. This is the minimum possible penalty.

The `ceil(a/b)` operation can be calculated using integer arithmetic as `(a + b - 1) / b`.

```java
import java.util.PriorityQueue;

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        // Max-heap to store {current_penalty, original_size, num_pieces}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        for (int num : nums) {
            pq.offer(new int[]{num, num, 1});
        }

        for (int i = 0; i < maxOperations; i++) {
            int[] top = pq.poll();
            int original_size = top[1];
            int num_pieces = top[2];

            if (original_size == num_pieces) { // Cannot split further
                pq.offer(top); // Put it back
                i--; // This operation was wasted, but constraints likely prevent this.
                continue;
            }

            int num_pieces_new = num_pieces + 1;
            // new_penalty = ceil(original_size / num_pieces_new)
            int new_penalty = (original_size + num_pieces_new - 1) / num_pieces_new;
            
            pq.offer(new int[]{new_penalty, original_size, num_pieces_new});
        }

        return pq.peek()[0];
    }
}
```
### Algorithm
- Create a max-heap to store objects or tuples representing `{current_penalty, original_size, num_pieces}`.
- For each `num` in the input array `nums`, add an entry `{num, num, 1}` to the heap.
- Iterate `maxOperations` times:
  - Pop the top element `{penalty, original_size, num_pieces}` from the heap, which represents the current largest penalty contribution.
  - Increment `num_pieces` by 1, signifying one operation is used to split this bag further.
  - Calculate the new penalty for this bag after the split: `new_penalty = ceil(original_size / num_pieces)`.
  - Push the new state `{new_penalty, original_size, num_pieces}` back into the heap.
- After the loop, the `penalty` of the top element in the heap is the minimized maximum penalty.

## Binary Search on the Answer
This problem asks to minimize a maximum value, which is a strong indicator that binary search on the answer is a viable strategy. Instead of finding the minimum penalty directly, we can ask a simpler decision question: "Is it possible to achieve a penalty of `p` using at most `maxOperations`?". This question is monotonic: if we can achieve a penalty of `p`, we can also achieve any penalty greater than `p`. This property allows us to binary search for the smallest `p` for which the answer to the decision question is "yes".
**Time:** O(N * log M), where N is the number of bags and M is the maximum possible number of balls in a bag. The binary search takes O(log M) iterations, and in each iteration, we check the possibility which takes O(N) time. · **Space:** O(1), as we only use a few variables to perform the binary search.
**Pros:** Highly efficient, especially when `maxOperations` is large. The runtime does not depend on `maxOperations`.; Guarantees finding the optimal solution within the time limits.
**Cons:** The concept of binary searching on the answer might be less intuitive than a direct greedy approach for some.
### Explanation
The range of possible answers for the minimum penalty is from 1 to the maximum number of balls in any single bag, `max(nums)`. Let's denote this range as `[low, high]`. We can perform a binary search on this range. For a given candidate penalty `mid`, we need to check if it's achievable.

To check if a penalty `p` is achievable, we calculate the total number of operations required to ensure no bag has more than `p` balls. For each bag `nums[i]`:
- If `nums[i] <= p`, no operations are needed for this bag.
- If `nums[i] > p`, we must split it. To make all resulting pieces have size at most `p`, we need to split it into `k = ceil(nums[i] / p)` pieces. This requires `k - 1` operations.

The number of operations for a bag `nums[i]` can be calculated with integer division as `(nums[i] - 1) / p`. This formula works even when `nums[i] <= p`, as it correctly yields 0.

We sum these required operations for all bags. If the total sum is less than or equal to `maxOperations`, then the penalty `p` is achievable.

The binary search proceeds as follows:
1. Set `low = 1`, `high = max(nums)` (or a sufficiently large number like `10^9`). `ans` can be initialized to `high`.
2. While `low <= high`:
    a. Calculate `mid = low + (high - low) / 2`.
    b. Check if penalty `mid` is achievable by calculating the required operations.
    c. If it is achievable (`required_ops <= maxOperations`), it means we might be able to do even better with a smaller penalty. So, we record `mid` as a potential answer (`ans = mid`) and try the lower half of the search space (`high = mid - 1`).
    d. If it's not achievable, the penalty `mid` is too small. We need to allow a larger penalty. So, we search in the upper half (`low = mid + 1`).

The final value of `ans` will be the minimum possible penalty.

```java
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int low = 1;
        int high = 0;
        for (int num : nums) {
            high = Math.max(high, num);
        }

        int minPenalty = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) { // Penalty must be at least 1
                low = 1;
                continue;
            }

            if (isPossible(nums, maxOperations, mid)) {
                minPenalty = mid;
                high = mid - 1; // Try for a smaller penalty
            } else {
                low = mid + 1; // Penalty is too small, need to increase
            }
        }
        return minPenalty;
    }

    // Helper function to check if a penalty 'p' is possible
    private boolean isPossible(int[] nums, int maxOperations, int p) {
        long requiredOps = 0;
        for (int num : nums) {
            // For a bag of size 'num', we need to split it into pieces of size at most 'p'.
            // Number of operations = ceil(num / p) - 1.
            // Using integer division, this is (num - 1) / p.
            requiredOps += (long)(num - 1) / p;
        }
        return requiredOps <= maxOperations;
    }
}
```
### Algorithm
- Define a search range for the penalty, `low = 1` and `high = max(nums)`.
- While `low <= high`:
  - Pick a `mid` value as the candidate penalty.
  - Check if this `mid` penalty is achievable using a helper function `isPossible(penalty)`.
  - The `isPossible(penalty)` function works as follows:
    - Initialize `operations_needed = 0`.
    - For each `num` in `nums`, the number of operations to make all its pieces at most `penalty` is `(num - 1) / penalty`. Add this to `operations_needed`.
    - Return `operations_needed <= maxOperations`.
  - If `isPossible(mid)` is true, it means `mid` is a valid penalty. We store it as a potential answer and try for an even smaller penalty by setting `high = mid - 1`.
  - Otherwise, `mid` is too small, and we need to allow a larger penalty, so we set `low = mid + 1`.
- Return the last valid penalty found.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinimumSize(int[] nums, int maxOperations) {
        int l = 1, r = nums.Max();
        while (l < r) {
            int mid = (l + r) >> 1;
            long s = 0;
            foreach(int x in nums) {
                s += (x - 1) / mid;
            }
            if (s <= maxOperations) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
```

### Java

```java
class Solution {
public
  int minimumSize(int[] nums, int maxOperations) {
    int left = 1, right = 0;
    for (int x : nums) {
      right = Math.max(right, x);
    }
    while (left < right) {
      int mid = (left + right) >> 1;
      long cnt = 0;
      for (int x : nums) {
        cnt += (x - 1) / mid;
      }
      if (cnt <= maxOperations) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} maxOperations * @return {number} */ var minimumSize =
  function (nums, maxOperations) {
    let left = 1;
    let right = Math.max(...nums);
    while (left < right) {
      const mid = (left + right) >> 1;
      let cnt = 0;
      for (const x of nums) {
        cnt += ~~((x - 1) / mid);
      }
      if (cnt <= maxOperations) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };

```

### CPP

```cpp
class Solution {
public:
  int minimumSize(vector<int> &nums, int maxOperations) {
    int left = 1, right = *max_element(nums.begin(), nums.end());
    while (left < right) {
      int mid = (left + right) >> 1;
      long long cnt = 0;
      for (int x : nums) {
        cnt += (x - 1) / mid;
      }
      if (cnt <= maxOperations) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int: def check(mx: int) -> bool: return sum((x - 1) // mx for x in nums) <= maxOperations return bisect_left(range(1, max(nums)), True, key=check) + 1

```