Removing Minimum Number of Magic Beans — LeetCode 2171 Python Solution

The problem

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.

Example

Input

beans = [4,1,6,5]

Output

4

Explanation

- We remove 1 bean from the bag with only 1 bean.

Python solution

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        s, n = sum(beans), len(beans)
        return min(s - x * (n - i) for i, x in enumerate(beans))

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2171. Removing Minimum Number of Magic Beans is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems