Removing Minimum Number of Magic Beans
Problem Description
You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.
Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.
Return the minimum number of magic beans that you have to remove.
Explanation
You have some bags of magic beans. Each bag contains a certain number of beans. The goal is to remove some beans so that all the remaining non-empty bags have the same number of beans.
For example:
If the bags have beans [4, 1, 6, 5] and you want all bags to have 4 beans, you:
Remove 2 bean from the bag with 6 beans.
Remove 1 bean from the bag with 5 beans.
Remove all beans from the bag with 1 bean.
The total beans removed here are 2+1+1=4. The task is to find the minimum beans you need to remove to make this happen for any target value.
Examples
Input: beans = [4,1,6,5]
Output: 4
Explanation:
- We remove 1 bean from the bag with only 1 bean.
This results in the remaining bags: [4,0,6,5]
- Then we remove 2 beans from the bag with 6 beans.
This results in the remaining bags: [4,0,4,5]
- Then we remove 1 bean from the bag with 5 beans.
This results in the remaining bags: [4,0,4,4]
We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that remove 4 beans or fewer.
Input: beans = [2,10,3,2]
Output: 7
Explanation:
- We remove 2 beans from one of the bags with 2 beans.
This results in the remaining bags: [0,10,3,2]
- Then we remove 2 beans from the other bag with 2 beans.
This results in the remaining bags: [0,10,3,0]
- Then we remove 3 beans from the bag with 3 beans.
This results in the remaining bags: [0,10,0,0]
We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that removes 7 beans or fewer.
Constraints:
- 1 <= beans.length <= 10^5
- 1 <= beans[i] <= 10^5
We will be analysing the solution with the brute force approach and prefix sum. Each approach has its own benefits and challenges regarding how fast it works and how much memory it uses.
Brute Force Approach
Intuition
What was the first approach that came to our mind is:
We can treat each bag's bean count as the "target" number of beans for the remaining non-empty bags.
For each target, we will calculate how many beans we must remove from all bags to achieve it.
Accordingly we will keep track of the smallest number of beans removed across all scenarios.
We will iterate each of the bag and keep the count of beans of each bag as the target. If a bag has fewer beans than the target, we can’t add beans (not allowed in the problem). So, we must remove all beans from such a bag.
If a bag has more beans than the target, we only remove the excess beans to match the target.
In this way, we can check all possible targets and by keeping track of the smallest value of beans removed, we can expect a correct output.
Approach
Initialize a variable to track the minimum beans removed:
- Set minRemoved to a very large value (infinity).
Iterate through each bag's bean count as a potential target value:
- For every element target in beans:Initialize beansRemoved to 0. This will track the total beans removed for the current target.
For the current target, calculate the total beans to be removed:For each bean in beans:If bean is greater than target, remove the excess beans:
Add (bean - target) to beansRemoved.If bean is less than target, remove all beans from that bag:
Add bean to beansRemoved.
Update the minimum beans removed:Compare beansRemoved with minRemoved.If beansRemoved is smaller, update minRemoved.
Repeat for all target values.
Return the smallest value of minRemoved as the result.
Lets Visualize with the below Video
Dry-Run
beans = [3, 7, 2, 5]
Output: 7
Step 1: Initialize Variables
- minRemoved = Infinity (to keep track of the minimum beans removed).
Step 2: Outer Loop – Iterate Over Each Target ValueFirst Target: 3
Set target = 3. Initialize beansRemoved = 0.
- Bag 1 (3 beans):
- 3 is already equal to the target. Remove 0 beans.
- beansRemoved = 0.
- Bag 2 (7 beans):
- 7 is greater than the target. Remove 7−3=4 beans.
- beansRemoved = 4.
- Bag 3 (2 beans):
- 2 is less than the target. Remove all 2 beans.
- beansRemoved = 4 + 2 = 6.
- Bag 4 (5 beans):
- 5 is greater than the target. Remove 5−3=2 beans.
- beansRemoved = 6 + 2 = 8.
Update minRemoved: min(∞,8)=8
Second Target: 7
Set target = 7. Initialize beansRemoved = 0.
- Bag 1 (3 beans):
- 3 is less than the target. Remove all 3 beans.
- beansRemoved = 3.
- Bag 2 (7 beans):
- 7 is already equal to the target. Remove 0 beans.
- beansRemoved = 3.
- Bag 3 (2 beans):
- 2 is less than the target. Remove all 2 beans.
- beansRemoved = 3 + 2 = 5.
- Bag 4 (5 beans):
- 5 is less than the target. Remove all 5 beans.
- beansRemoved = 5 + 5 = 10.
Update minRemoved: min(8,10)=8.
Third Target: 2
Set target = 2. Initialize beansRemoved = 0.
- Bag 1 (3 beans):
- 3 is greater than the target. Remove 3−2=1 beans.
- beansRemoved = 1.
- Bag 2 (7 beans):
- 7 is greater than the target. Remove 7−2=57 - 2 = 57−2=5 beans.
- beansRemoved = 1 + 5 = 6.
- Bag 3 (2 beans):
- 2 is already equal to the target. Remove 0 beans.
- beansRemoved = 6.
- Bag 4 (5 beans):
- 5 is greater than the target. Remove 5−2=3 beans.
- beansRemoved = 6 + 3 = 9.
Update minRemoved: min(8,9)=8.
Fourth Target: 5
Set target = 5. Initialize beansRemoved = 0.
- Bag 1 (3 beans):
- 3 is less than the target. Remove all 3 beans.
- beansRemoved = 3.
- Bag 2 (7 beans):
- 7 is greater than the target. Remove 7−5=2 beans.
- beansRemoved = 3 + 2 = 5.
- Bag 3 (2 beans):
- 2 is less than the target. Remove all 2 beans.
- beansRemoved = 5 + 2 = 7.
- Bag 4 (5 beans):
- 5 is already equal to the target. Remove 0 beans.
- beansRemoved = 7.
Update minRemoved: min(8,7)=7.
Final Step: Return the Result
The minimum beans removed across all targets is 7.
Brute Force Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
// Initialize the minimum beans to be removed as the maximum possible value
long long minRemoved = LLONG_MAX;
// Iterate over each bag's bean count as a potential target
for (int target : beans) {
// Initialize the total beans to be removed for the current target
long long beansRemoved = 0;
// Calculate the beans to be removed for the current target
for (int bean : beans) {
// If the current bag has more beans than the target, remove the excess
if (bean > target) {
beansRemoved += (bean - target);
}
// If the current bag has fewer beans than the target, remove all beans
else if (bean < target) {
beansRemoved += bean;
}
}
// Update the minimum beans to be removed across all targets
minRemoved = min(minRemoved, beansRemoved);
}
// Return the minimum beans to be removed
return minRemoved;
}
};2. Java Try on Compiler
class Solution {
public long minimumRemoval(int[] beans) {
long minRemoved = Long.MAX_VALUE;
// Step 1: Iterate over each value in the array as the target
for (int i = 0; i < beans.length; i++) {
int target = beans[i];
long beansRemoved = 0;
// Step 2: Calculate beans to remove for this target
for (int j = 0; j < beans.length; j++) {
if (beans[j] > target) {
// Remove excess beans
beansRemoved += (beans[j] - target);
} else if (beans[j] < target) {
// Remove all beans if less than target
beansRemoved += beans[j];
}
}
// Step 3: Track the minimum beans removed
minRemoved = Math.min(minRemoved, beansRemoved);
}
return minRemoved;
}
}
3. Python Try on Compiler
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
# Initialize the minimum beans to be removed as infinity
min_removed = float('inf')
# Iterate over each bag's bean count as a potential target
for target in beans:
# Initialize the total beans to be removed for the current target
beans_removed = 0
# Calculate the beans to be removed for the current target
for bean in beans:
# If the current bag has more beans than the target, remove the excess
if bean > target:
beans_removed += (bean - target)
# If the current bag has fewer beans than the target, remove all beans
elif bean < target:
beans_removed += bean
# Update the minimum beans to be removed across all targets
min_removed = min(min_removed, beans_removed)
# Return the minimum beans to be removed
return min_removed
4. JavaScript Try on Compiler
var minimumRemoval = function(beans) {
let minRemoved = Number.MAX_SAFE_INTEGER;
// Iterate over each bag's bean count as a potential target
for (let target of beans) {
// Initialize the total beans to be removed for the current target
let beansRemoved = 0;
// Calculate the beans to be removed for the current target
for (let bean of beans) {
// If the current bag has more beans than the target, remove the excess
if (bean > target) {
beansRemoved += (bean - target);
}
// If the current bag has fewer beans than the target, remove all beans
else if (bean < target) {
beansRemoved += bean;
}
}
// Update the minimum beans to be removed across all targets
minRemoved = Math.min(minRemoved, beansRemoved);
}
// Return the minimum beans to be removed
return minRemoved;
};Time Complexity: O(n^2)
The brute force approach involves two nested loops:
Outer Loop: Iterates over each value in the array beans as the potential target.
- Runs for n iterations, where n is the size of the array.
Inner Loop: For each target, iterates over all the values in the array to calculate the total beans removed.
- Runs for n iterations per target.
Thus, the time complexity of the approach is: O(n×n)=O(n^2).
Space Complexity: O(1)
Auxiliary space refers to the extra space used by the algorithm, excluding the input data.
We are using only a few variables for tracking:
- minRemoved: A long to store the minimum value.
- beansRemoved: A long to store the running total of beans removed.
Since these variables are constant, the auxiliary space complexity is: O(1)
Total Space Complexity
Total space includes the space used by both the input and any auxiliary space.
- The input array beans requires O(n) space.
- The auxiliary space is O(1) (as explained above).
Thus, the total space complexity is: O(n).
Reviewing the constraints for the given question which is "1 <= nums.length <= 10^5" will result in Time Limit Exceeded for the Brute Force Approach.
The interviewer will be unhappy with the approach, we need to figure out an optimal solution.
Optimal Approach
Intuition
Before moving to the optimal solution let us first analyse where could we have done the optimization for the Brute force approach.
We selected one number from the array as the target number of beans for all the bags.
If we pick a specific number from the array as the target (let's call it beans[i]), we will have to remove:
- Excess Beans from Bags Greater than the Target: If a bag has more beans than the target, you need to remove the difference.
- All Beans from Bags Less Than the Target: If a bag has fewer beans than the target, you need to remove all the beans from that bag.
This resulted in the time complexity of O(n^2).
What can we do to optimize it ?
Instead of recalculating the total number of beans in every iteration, we compute the total sum once at the beginning. This way, we don't need to traverse the entire array every time to get the total sum of beans.
Next, how can we figure out a optimal method to know how many beans to be removed each time ?
In the brute force approach, we calculate the number of beans to remove for every target value by iterating through the entire array multiple times.
In the optimal approach, we can use a more mathematical approach:
For each target beans[i], we compute the number of beans to remove as
beans removed = total sum of beans − (n×target)The idea behind this formula is:
For any target value beans[i], we calculate how many beans remain in all the bags after adjusting to that target: We don’t have to iterate through every bag again and calculate the difference manually. Instead, we compute the total beans and then calculate how much we would "keep" if all bags had the same number of beans (beans[i]).The "kept" beans are simply n * beans[i], because:If a bag has more than beans[i] beans, we’ll remove the difference.If a bag has fewer than beans[i] beans, we’ll empty it.Every bag would contain exactly beans[i] beans. So, the total remaining beans would be beans[i] for each of the n bags, i.e., n * beans[i].
Hence , the number of beans to remove is the total sum of beans minus the remaining beans (n * beans[i]).
We can optimize it more !!
Sorting the array before starting the removal process ensures that we are efficiently checking from the smallest possible target to the largest.
This step allows us to directly use the above formula without worrying about iterating multiple times over the array to calculate beans removed.
Approach
Sort the Array
Sorting the array allows us to pick a target value in increasing order. This simplifies how we handle smaller and larger values relative to the target.
Precompute the Total Sum
Calculate the total sum of all beans in the array. This helps in quickly determining how many beans remain after setting a target.
Iteratively Test Each Target
For each element beans[i] in the sorted array:
- The target is beans[i].
- For all elements to the right (larger than the target), calculate their contribution using: beansRemovedFromRight=sum of all elements−number of elements × target value
- Elements to the left (smaller than the target) are removed entirely. This is implicitly handled since we decrement the sum as we move forward.
Track the Minimum Beans Removed
Keep track of the minimum total beans removed across all targets.
Dry-Run
beans = [3, 7, 2, 5]
Output: 7
Step 1: Sort the Input Array
- Input: beans = [3, 7, 2, 5]
- After sorting: beans = [2, 3, 5, 7]
Step 2: Calculate Total Sum of Beans
Initialize sum = 0
Iterate through beans to compute the total sum:
- Add 2: sum = 2
- Add 3: sum = 5
- Add 5: sum = 10
- Add 7: sum = 17
So, the total sum of beans is sum = 17.
Step 3: Iterate Through Each Bag
- Initialize result = Long.MAX_VALUE
- m = beans.length = 4 (initial number of bags)
For each bag, calculate the total beans removed and update result:
Iteration 1: i = 0, beans[i] = 2
- Remaining bags (m) = 4
- Calculate beans to keep in all bags: m * beans[i] = 4 * 2 = 8
- Beans to remove = sum - m * beans[i] = 17 - 8 = 9
- Update result = min(Long.MAX_VALUE, 9) = 9
Iteration 2: i = 1, beans[i] = 3
- Remaining bags (m) = 3
- Calculate beans to keep in all bags: m * beans[i] = 3 * 3 = 9
- Beans to remove = sum - m * beans[i] = 17 - 9 = 8
- Update result = min(9, 8) = 8
Iteration 3: i = 2, beans[i] = 5
- Remaining bags (m) = 2
- Calculate beans to keep in all bags: m * beans[i] = 2 * 5 = 10
- Beans to remove = sum - m * beans[i] = 17 - 10 = 7
- Update result = min(8, 7) = 7
Iteration 4: i = 3, beans[i] = 7
- Remaining bags (m) = 1
- Calculate beans to keep in all bags: m * beans[i] = 1 * 7 = 7
- Beans to remove = sum - m * beans[i] = 17 - 7 = 10
- Update result = min(7, 10) = 7
Final Step: Return result
- After iterating through all the bags, the minimum beans removed is 7.
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
// Sort the array to facilitate optimal calculation
sort(beans.begin(), beans.end());
// Calculate the total sum of beans
long long sum = 0;
for (int bean : beans) {
sum += bean;
}
// Initialize the result with a very large value
long long result = LLONG_MAX;
long long m = beans.size();
// Iterate over each unique number in the sorted array
for (size_t i = 0; i < beans.size(); i++, m--) {
// Calculate the minimum beans removed for the current target
result = min(result, sum - m * beans[i]);
}
// Return the minimum number of beans removed
return result;
}
};2. Java Try on Compiler
class Solution {
public long minimumRemoval(int[] beans) {
// Sort the array to facilitate optimal calculation
Arrays.sort(beans);
// Calculate the total sum of beans
long sum = 0;
for (int bean : beans) {
sum += bean;
}
// Initialize the result with a very large value
long result = Long.MAX_VALUE;
long m = beans.length;
// Iterate over each unique number in the sorted array
for (int i = 0; i < beans.length; i++, m--) {
// Calculate the minimum beans removed for the current target
result = Math.min(result, sum - m * beans[i]);
}
// Return the minimum number of beans removed
return result;
}
}
3. Python Try on Compiler
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
# Sort the array to facilitate optimal calculation
beans.sort()
# Calculate the total sum of beans
total_sum = sum(beans)
# Initialize the result with a very large value
result = float('inf')
m = len(beans)
# Iterate over each unique number in the sorted array
for i in range(len(beans)):
# Calculate the minimum beans removed for the current target
result = min(result, total_sum - m * beans[i])
m -= 1
# Return the minimum number of beans removed
return result4. JavaScript Try on Compiler
var minimumRemoval = function(beans) {
// Sort the array to facilitate optimal calculation
beans.sort((a, b) => a - b);
// Calculate the total sum of beans
let totalSum = beans.reduce((acc, bean) => acc + bean, 0);
// Initialize the result with a very large value
let result = Number.MAX_SAFE_INTEGER;
let m = beans.length;
// Iterate over each unique number in the sorted array
for (let i = 0; i < beans.length; i++) {
// Calculate the minimum beans removed for the current target
result = Math.min(result, totalSum - m * beans[i]);
m--;
}
// Return the minimum number of beans removed
return result;
};Time Complexity: O(nlogn)
Time Complexity
Sorting the Array:
- Sorting takes O(nlogn), where n is the length of the beans array.
Iterating Over the Sorted Array:
- The single loop over the sorted array to calculate the minimum removals runs in O(n).
Overall Time Complexity:
- Dominated by the sorting step, so the total time complexity is: O(nlogn)+O(n)=O(nlogn)
Space Complexity: O(1)
Auxiliary Space Complexity:
- Temporary Variables:
Variables such as sum, result, and m are scalar variables, requiring O(1)space.
Total Auxiliary Space Complexity:O(1)
Total Space Compexity
- Input Array:
The array beans is passed as input, consuming O(n) space.
Auxiliary Space:As discussed, it is O(1).
Hence, the Total Space Complexity: O(1) + O(n) = O(n).
Learning Tip
You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.
Given an integer array nums, find the subarray with the largest sum, and return its sum.