2171. Removing Minimum Number of Magic Beans LeetCode Solution

In this guide, you will get 2171. Removing Minimum Number of Magic Beans LeetCode Solution with the best time and space complexity. The solution to Removing Minimum Number of Magic Beans problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Removing Minimum Number of Magic Beans solution in C++
Removing Minimum Number of Magic Beans solution in Java
Removing Minimum Number of Magic Beans solution in Python
Additional Resources

2171. Removing Minimum Number of Magic Beans LeetCode Solution image

Problem Statement of Removing Minimum Number of Magic Beans

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.

Example 1:

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.

Example 2:

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 <= 105
1 <= beans[i] <= 105

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

2171. Removing Minimum Number of Magic Beans LeetCode Solution in C++

class Solution {
 public:
  long long minimumRemoval(vector<int>& beans) {
    const long n = beans.size();
    const long sum = accumulate(beans.begin(), beans.end(), 0L);
    long ans = LONG_MAX;

    ranges::sort(beans);

    for (int i = 0; i < n; ++i)
      ans = min(ans, sum - (n - i) * beans[i]);

    return ans;
  }
};
/* code provided by PROGIEZ */

2171. Removing Minimum Number of Magic Beans LeetCode Solution in Java

class Solution {
  public long minimumRemoval(int[] beans) {
    final long n = beans.length;
    final long sum = Arrays.stream(beans).asLongStream().sum();
    long ans = Long.MAX_VALUE;

    Arrays.sort(beans);

    for (int i = 0; i < n; ++i)
      ans = Math.min(ans, sum - (n - i) * beans[i]);

    return ans;
  }
}
// code provided by PROGIEZ

2171. Removing Minimum Number of Magic Beans LeetCode Solution in Python

class Solution:
  def minimumRemoval(self, beans: list[int]) -> int:
    n = len(beans)
    summ = sum(beans)
    return min(summ - (n - i) * bean
               for i, bean in enumerate(sorted(beans)))
 # code by PROGIEZ