Problem Description

You have an array beans where each element represents the number of magic beans in a bag. Each value in the array is a positive integer.

Your task is to remove beans from the bags following these rules:

• You can remove any number of beans from each bag (including removing zero beans)
• After removal, all non-empty bags must contain the same number of beans
• A bag is considered non-empty if it has at least one bean remaining
• Once you remove a bean from a bag, you cannot put it back

The goal is to find the minimum total number of beans you need to remove to achieve this equal distribution among all non-empty bags.

For example, if you have bags with [4, 1, 6, 5] beans, one possible solution is to:

• Remove 1 bean from the first bag (making it 3)
• Remove 1 bean from the second bag (making it 0, thus empty)
• Remove 3 beans from the third bag (making it 3)
• Remove 2 beans from the fourth bag (making it 3)

This results in bags with [3, 0, 3, 3] beans, where all non-empty bags have exactly 3 beans. The total beans removed is 1 + 1 + 3 + 2 = 7.

The solution approach sorts the array and considers each unique bean count as a potential target. For each potential target beans[i], it calculates how many beans would remain if all bags with at least beans[i] beans are reduced to exactly beans[i] beans (and bags with fewer beans are emptied). The formula s - beans[i] * (n - i) computes the beans to remove, where s is the total sum of all beans and (n - i) is the number of bags that will remain non-empty.

Intuition

The key insight is that once we decide on a target number of beans for all non-empty bags, we have a clear strategy: bags with more beans get reduced to the target, and bags with fewer beans must be completely emptied (since we can't add beans back).

Why does sorting help? When we sort the array, we can observe that if we choose a target value, all bags to its left (with fewer beans) must be emptied, while all bags to its right (with more or equal beans) can be reduced to that target value.

Consider the sorted array [1, 4, 5, 6]. If we choose 4 as our target:

• The bag with 1 bean must be emptied (remove 1 bean)
• The bag with 4 beans stays as is (remove 0 beans)
• The bag with 5 beans reduces to 4 (remove 1 bean)
• The bag with 6 beans reduces to 4 (remove 2 beans)

The brilliant part is recognizing that we only need to consider values that already exist in the array as potential targets. Why? Because if we choose any value between two existing values, we might as well choose the smaller one - it won't increase the number of bags we need to empty, but it will reduce the amount we need to remove from larger bags.

For each potential target beans[i] in the sorted array:

• Bags at positions 0 to i-1 will be emptied completely
• Bags at positions i to n-1 will have exactly beans[i] beans

The total beans remaining would be beans[i] * (n - i) where (n - i) is the count of non-empty bags. Since we know the total sum s of all beans initially, the beans to remove is simply s - beans[i] * (n - i).

By trying each value in the sorted array as a potential target and calculating the removal cost, we can find the minimum.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

The implementation follows a straightforward approach based on sorting and enumeration:

Step 1: Sort the array

beans.sort()

We sort the beans array in ascending order. This allows us to efficiently determine which bags to empty and which to keep for any chosen target value.

Step 2: Calculate the total sum and array length

s, n = sum(beans), len(beans)

• s stores the total number of beans across all bags
• n stores the number of bags

Step 3: Enumerate all possible target values

return min(s - x * (n - i) for i, x in enumerate(beans))

This line does the heavy lifting through a generator expression:

• We iterate through each index i and value x in the sorted beans array
• For each position i, we consider x = beans[i] as the target number of beans for non-empty bags
• The calculation s - x * (n - i) computes the beans to remove:
  • (n - i) is the number of bags from position i to the end (these will remain non-empty)
  • x * (n - i) is the total beans that will remain after removal
  • s - x * (n - i) is the difference, which equals the beans we need to remove

Why this formula works:

• All bags at indices 0 to i-1 have fewer than x beans and must be emptied completely
• All bags at indices i to n-1 have at least x beans and will be reduced to exactly x beans
• The sum of beans to remove from left side: sum(beans[0] to beans[i-1])
• The sum of beans to remove from right side: sum(beans[i] to beans[n-1]) - x * (n - i)
• Total removal = sum(all beans) - x * (n - i) = s - x * (n - i)

The min() function finds the minimum removal cost across all possible target values.

Time Complexity: O(n log n) for sorting + O(n) for enumeration = O(n log n)
Space Complexity: O(1) if we don't count the space used by sorting

Example Walkthrough

Let's walk through the solution with a small example: beans = [4, 1, 6, 5]

Step 1: Sort the array After sorting: beans = [1, 4, 5, 6]

Step 2: Calculate total sum and length

• s = 1 + 4 + 5 + 6 = 16 (total beans)
• n = 4 (number of bags)

Step 3: Try each value as a potential target

Let's evaluate each position as our target:

Option 1: Target = 1 (index 0)

• Keep bags from index 0 to 3 (all 4 bags) with 1 bean each
• Final distribution: [1, 1, 1, 1]
• Beans remaining: 1 × 4 = 4
• Beans to remove: 16 - 4 = 12

Option 2: Target = 4 (index 1)

• Empty bag at index 0 (has 1 bean)
• Keep bags from index 1 to 3 with 4 beans each
• Final distribution: [0, 4, 4, 4]
• Beans remaining: 4 × 3 = 12
• Beans to remove: 16 - 12 = 4

Option 3: Target = 5 (index 2)

• Empty bags at indices 0 and 1 (have 1 and 4 beans)
• Keep bags from index 2 to 3 with 5 beans each
• Final distribution: [0, 0, 5, 5]
• Beans remaining: 5 × 2 = 10
• Beans to remove: 16 - 10 = 6

Option 4: Target = 6 (index 3)

• Empty bags at indices 0, 1, and 2 (have 1, 4, and 5 beans)
• Keep only the last bag with 6 beans
• Final distribution: [0, 0, 0, 6]
• Beans remaining: 6 × 1 = 6
• Beans to remove: 16 - 6 = 10

Step 4: Find the minimum Comparing all options: min(12, 4, 6, 10) = 4

The optimal solution is to use 4 as the target, removing only 4 beans total. The final distribution would be [0, 4, 4, 4] in the original order (since the original array was [4, 1, 6, 5]).

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(n log n), where n is the number of bags (length of the beans array). This complexity comes from:

• Sorting the beans array: O(n log n) using Python's Timsort algorithm
• Calculating the sum of all beans: O(n)
• Iterating through the sorted array and computing the minimum: O(n)

Since sorting dominates the complexity, the overall time complexity is O(n log n).

The space complexity is O(log n). This comes from:

• The sorting operation uses O(log n) space for the recursion stack in Timsort's merge operations
• The variables s, n, and loop variables use O(1) constant space
• The generator expression in the min function doesn't create additional storage, processing values one at a time

Therefore, the total space complexity is O(log n), dominated by the sorting algorithm's auxiliary space requirements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Duplicate Values Inefficiently

The current solution processes duplicate values multiple times, which doesn't affect correctness but can be inefficient for arrays with many duplicates.

Example Problem:

beans = [1, 1, 1, 1, 1, 5, 5, 5, 5, 5]

The algorithm will calculate the same target value (1 or 5) multiple times unnecessarily.

Solution: Deduplicate the target values before processing:

def minimumRemoval(self, beans: List[int]) -> int:
    beans.sort()
    total_sum = sum(beans)
    n = len(beans)
  
    min_removals = float('inf')
    prev_value = -1
  
    for i, bean_count in enumerate(beans):
        # Skip duplicate values
        if bean_count == prev_value:
            continue
        prev_value = bean_count
      
        removals = total_sum - bean_count * (n - i)
        min_removals = min(min_removals, removals)
  
    return min_removals

2. Integer Overflow in Other Languages

While Python handles large integers automatically, implementing this in languages like C++ or Java requires careful consideration of integer overflow when calculating total_sum.

Example Problem:

beans = [10^9, 10^9, 10^9, ...]  # Many large values

Solution: Use appropriate data types (e.g., long long in C++ or long in Java) for sum calculations.

3. Misunderstanding the Problem - Trying to Redistribute Beans

A conceptual pitfall is thinking you can redistribute beans between bags rather than only removing them. The problem explicitly states removed beans cannot be put back.

Incorrect Thinking: "I can take 2 beans from bag A and give them to bag B"

Correct Understanding: "I can only remove beans; redistribution is not allowed"

4. Not Considering Empty Bags in the Final State

Some might mistakenly try to ensure all bags (including empty ones) have the same count, which would force all bags to be empty.

Wrong Interpretation: All bags must have the same number (including zeros)

Correct Interpretation: Only non-empty bags need to have the same count; bags can be emptied completely