Remove the Fewest Units to Equalize Nonempty Bags
Company: Deshaw
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Each positive entry of `beans` gives the number of beans in one bag. You may remove any number from each bag, including removing all of them, but cannot move or put removed beans back. Make every remaining nonempty bag contain the same number of beans. Return the minimum total number of beans that must be removed.
```cpp
class Solution {
public:
long long minimumRemoval(vector<int>& beans);
};
```
### Examples
**Example 1:**
```text
beans = [2,4,4]
Output: 2
Explanation: Empty the size-two bag and keep the two size-four bags.
```
**Example 2:**
```text
beans = [3,3,3]
Output: 0
Explanation: All nonempty bags already agree.
```
### Constraints
- `1 <= beans.length <= 10^5`.
- `1 <= beans[i] <= 10^5`.
### Clarifying Questions
Empty bags are ignored by the equality condition. Beans cannot be moved between bags or put back after removal.
```hint Inspect the structure
For one positive target size, should any bag already large enough be discarded?
```
### Reasoning checkpoints
- Apply the equality requirement only to nonempty bags and never increase a bag's contents.
- Show that the proposed removals can achieve the goal and that no other choice removes fewer beans.
- Handle repeated bag sizes and totals beyond 32-bit range.
### Optional extensions
How can you justify that the set of final bag sizes you consider includes an optimum?
Overview: Remove the Fewest Units to Equalize Nonempty Bags. The positive entries of beans are bag contents. You may remove any number of units from each bag, including emptying it. Every remaining nonempty bag must have the same size; removed units cannot be moved or restored. Return the fewest removed units.