2171. Removing Minimum Number of Magic Beans

MediumArrayPrefix SumSorting
Leetcode Link

Problem Description

The LeetCode problem provides us with an array beans, in which each element represents the number of magic beans in a respective bag. Our task is to make the number of beans in each non-empty bag equal by removing beans from the bags. There are two conditions we need to obey:

  1. We cannot add beans back to any bag once removed.
  2. After the removal, no bag should be empty; each should contain at least one bean.

The goal is to determine the minimum number of beans that we need to eliminate to achieve equal amounts in all non-empty bags.

Intuition

To solve the problem, one might initially consider trying to make all bags have the same number of beans as the bag with the least amount, but that is not necessarily optimal. To minimize bean removal, we must intelligently decide which beans to remove while taking into account the total bean count.

Given that we want all the non-empty bags to have an equal number of beans, a sensible approach is to make them all equal to a certain number and we never want that number to be more than the smallest non-zero number of beans in any bag. Therefore, we can sort beans array first, which helps us consider potential equal bean counts in order.

While iterating through the sorted array, we will simulate making all non-empty bags have the same number of beans as the current bag. The number of beans to remove will then be the total sum of beans minus the beans in the current bag times the number of remaining bags. This is because each remaining bag will have the same number of beans as the current bag, so we multiply that by the remaining bags count (including the current bag).

We repeat this process for each bag and keep track of the smallest number of beans we need to remove. This will give us the answer.

Learn more about Prefix Sum and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The implementation uses a simple algorithm and takes advantage of the sorted properties of the array to reduce the number of beans removed to a minimum.

Here's the step-by-step approach, paired with the code provided:

  1. Sort the beans array.

    1beans.sort()

    Sorting the array allows us to approach the problem in ascending order of bean counts, ensuring we always consider equalizing to the smallest possible non-zero count.

  2. Initialize the variable ans to the sum of beans; this represents the total count that will be considered for potential removal.

    1ans = s = sum(beans)

  3. Calculate the length of beans array and store it in variable n.

    1n = len(beans)

  4. Iterate through each bag via its index i and the value v representing the number of beans in the current bag.

    1for i, v in enumerate(beans):

  5. Calculate the number of beans to be removed if we make all non-empty bags equal to the current bag's bean count.

    1ans = min(ans, s - v * (n - i))

    The mathematical formula here is crucial. s - v * (n - i) calculates the total number of beans to be removed if we decide that each remaining bag (including the current one) should contain v beans.

    • s is the total initial number of beans.
    • v is the targeted number of beans for each bag.
    • n - i count of bags including and after the current one to be equalized.

    We subtract from the total (s) the product of the targeted number of beans (v) and the remaining bags (n - i), which would give us the count of beans left if we were to equalize all bags to the current count v.

  6. Return the smallest value of ans found through the iteration, which represents the minimum removal.

    1return ans

This algorithm is efficient because it leverages the sorting of the array, which provides a natural order to consider potential equal bean counts. The only significant data structure used is the list itself for storing and iterating over the bean counts. The simplicity and efficiency of this solution come from not needing a more complex data structure or pattern, as the problem can be solved with a single pass through a sorted array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's illustrate the solution approach using a small example. Given the array beans = [4, 1, 6, 5], we want to make the number of magic beans in each non-empty bag equal by removing the least number of beans possible, with the rule that no bags can be empty after the removal.

  1. First, we sort the beans array to have beans = [1, 4, 5, 6].

  2. We initialize ans to the sum of beans, which is in this case 1 + 4 + 5 + 6 = 16. At the same time, we store this sum in the variable s.

  3. We calculate the length of beans array, n = 4.

  4. Now, we start iterating through the sorted beans array. On each iteration, we have the index i and the beans number v for each bag.

  5. As we iterate, we calculate the beans to be removed if we make all non-empty bags have v beans (the current bean count in our iteration):

    • With i=0, v=1: We could remove no beans, as every bag including and after can be 1. But since there is the maximum number of bags here, this isn't optimal.
    • With i=1, v=4: ans = min(16, 16 - 4 * (4-1)) which simplifies to ans = min(16, 16 - 12) resulting in ans = 4.
    • With i=2, v=5: ans = min(4, 16 - 5 * (4-2)) which simplifies to ans = min(4, 16 - 10) resulting in ans = 4.
    • With i=3, v=6: ans = min(4, 16 - 6 * (4-3)) which is ans = min(4, 16 - 6) resulting in ans = 4.

  6. After iterating through each bag, the smallest number of beans to remove is 4. Hence, the answer to the problem is 4, which is achieved by making all non-empty bags have 4 magic beans each (equalizing to the bag with 4 beans in it).

By following this algorithm, we ensure we are checking every possible scenario to find the minimum beans we need to remove in order to make the bags equal without leaving any empty, doing so efficiently by piggybacking off of the sorted nature of beans.

Solution Implementation

1class Solution:
2    def minimumRemoval(self, beans: List[int]) -> int:
3        # Sort the list of beans to enable uniform removal
4        beans.sort()
5        # Calculate the sum of all the beans, this also represents
6        # the initial answer before any removals
7        total_sum = sum(beans)
8        # Number of bean piles
9        num_piles = len(beans)
10        # Initialize the minimum removals with the total sum as the upper bound
11        min_removals = total_sum
12        # Iterate through the sorted bean piles
13        for i, num_beans in enumerate(beans):
14            # Calculate the current total after removing beans from the current pile onwards.
15            # This means all piles to the right side of the current one (inclusive)
16            # will have 'num_beans' beans.
17            # The total beans removed will be the original sum minus the beans left.
18            current_total = total_sum - num_beans * (num_piles - i)
19            # Update the minimum removals if the current total is lower.
20            min_removals = min(min_removals, current_total)
21        # Return the minimum number of beans that needs to be removed
22        return min_removals
23
1class Solution {
2    public long minimumRemoval(int[] beans) {
3        // Sort the array to allow the calculation of removals based on ascending bean quantities.
4        Arrays.sort(beans);
5
6        // Calculate the total sum of beans to prepare for further calculations.
7        long totalBeans = 0;
8        for (int beanCount : beans) {
9            totalBeans += beanCount;
10        }
11
12        // Initialize the answer with the total sum, assuming no removals are made yet.
13        long minRemovals = totalBeans;
14      
15        // Calculate the minimum removals needed by trying to make all piles equal to each pile's number of beans.
16        int numOfPiles = beans.length;
17        for (int i = 0; i < numOfPiles; ++i) {
18            // Calculate the beans to remove if all piles were to be made equal to the current pile's beans.
19            long beansToRemove = totalBeans - (long) beans[i] * (numOfPiles - i);
20            // Update minRemovals if the current calculation yields a smaller number of beans to remove.
21            minRemovals = Math.min(minRemovals, beansToRemove);
22        }
23
24        // Return the minimum removals necessary to make all piles have an equal number of beans.
25        return minRemovals;
26    }
27}
28
1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5class Solution {
6public:
7    long long minimumRemoval(vector<int>& beans) {
8        // Sort the beans vector to ensure increasing order
9        sort(beans.begin(), beans.end());
10      
11        // Calculate the sum of all elements in the beans vector
12        long long totalBeans = accumulate(beans.begin(), beans.end(), 0ll);
13      
14        // Initialize the answer with the total beans as the worst case
15        long long minimumBeansToRemove = totalBeans;
16      
17        int numberOfBags = beans.size(); // Store the number of bags
18      
19        // Iterate through the sorted beans vector
20        for (int index = 0; index < numberOfBags; ++index) {
21            // Calculate the number of beans to remove if all bags have beans[i] beans
22            // This is done by subtracting the total number of beans that would remain if 
23            // all remaining bags had beans[index] beans from the initial sum 'totalBeans'
24            long long beansToRemove = totalBeans - 1ll * beans[index] * (numberOfBags - index);
25          
26            // Update the result with the minimum number of beans to remove found so far
27            minimumBeansToRemove = min(minimumBeansToRemove, beansToRemove);
28        }
29      
30        // Return the result which is the minimum number of beans to remove
31        // such that all the remaining non-empty bags have the same number of beans
32        return minimumBeansToRemove;
33    }
34};
35
1function minimumRemoval(beans: number[]): number {
2    // Calculate the total number of beans.
3    let totalBeans = beans.reduce((accumulator, current) => accumulator + current, 0);
4
5    // Sort the array of beans in ascending order for easier processing.
6    beans.sort((a, b) => a - b);
7
8    // Initialize the answer with the total number, as a worst-case scenario.
9    let minBeansToRemove = totalBeans;
10
11    const numOfBeans = beans.length;
12
13    // Iterate through the beans array to find the minimum beans to remove.
14    for (let index = 0; index < numOfBeans; index++) {
15        // Calculate the total beans to remove if we make all the bags equal to beans[index].
16        let currentRemoval = totalBeans - beans[index] * (numOfBeans - index);
17
18        // Update minBeansToRemove to the minimum of the current removal and previous minimum.
19        minBeansToRemove = Math.min(currentRemoval, minBeansToRemove);
20    }
21
22    // Return the minimum number of beans to remove.
23    return minBeansToRemove;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

The given Python code snippet is designed to find the minimum number of beans that need to be removed so that all the remaining piles have the same number of beans. It first sorts the beans list, calculates the sum of all beans, and then iterates through the sorted list to find the minimum number of beans to remove.

Time Complexity

The time complexity of the code is determined by the sorting step and the iteration step.

  1. Sorting the beans list takes O(nlogn) time, where n is the number of elements in the beans list. This is because the .sort() method in Python uses TimSort, which has this time complexity.

  2. The for loop iterates over the sorted list exactly once, which takes O(n) time.

Combining these two steps, the overall time complexity is O(nlogn) as this is the dominating term.

Space Complexity

As for space complexity:

  1. The sorting operation is done in-place, and does not require additional space proportional to the input size, so its space complexity is O(1).

  2. The variables ans, s, and n, and the iteration using i and v require constant space, which is also O(1).

Therefore, the overall space complexity of the function is O(1), indicating that it uses a constant amount of extra space.

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

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫