2171. Removing Minimum Number of Magic Beans
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:
- We cannot add beans back to any bag once removed.
- 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.
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:
-
Sort the
beans
array.beans.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.
-
Initialize the variable
ans
to the sum ofbeans
; this represents the total count that will be considered for potential removal.ans = s = sum(beans)
-
Calculate the length of
beans
array and store it in variablen
.n = len(beans)
-
Iterate through each bag via its index
i
and the valuev
representing the number of beans in the current bag.for i, v in enumerate(beans):
-
Calculate the number of beans to be removed if we make all non-empty bags equal to the current bag's bean count.
ans = 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 containv
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 countv
. -
Return the smallest value of
ans
found through the iteration, which represents the minimum removal.return 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
First, we sort the
beans
array to havebeans = [1, 4, 5, 6]
. -
We initialize
ans
to the sum ofbeans
, which is in this case 1 + 4 + 5 + 6 = 16. At the same time, we store this sum in the variables
. -
We calculate the length of
beans
array,n = 4
. -
Now, we start iterating through the sorted
beans
array. On each iteration, we have the indexi
and the beans numberv
for each bag. -
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 toans = min(16, 16 - 12)
resulting inans = 4
. - With i=2, v=5:
ans = min(4, 16 - 5 * (4-2))
which simplifies toans = min(4, 16 - 10)
resulting inans = 4
. - With i=3, v=6:
ans = min(4, 16 - 6 * (4-3))
which isans = min(4, 16 - 6)
resulting inans = 4
.
-
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
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.
-
Sorting the
beans
list takesO(nlogn)
time, wheren
is the number of elements in thebeans
list. This is because the.sort()
method in Python uses TimSort, which has this time complexity. -
The
for
loop iterates over the sorted list exactly once, which takesO(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:
-
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)
. -
The variables
ans
,s
, andn
, and the iteration usingi
andv
require constant space, which is alsoO(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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
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 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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!