We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Removing Minimum Number of Magic Beans

Difficulty: Medium

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. Return the minimum number of magic beans that you have to remove.

Key Insights

  • The goal is to make the number of beans in the remaining non-empty bags equal.
  • We need to find a target number of beans that can be achieved by removing the minimum possible number of beans.
  • Sorting the array helps in efficiently determining how many beans need to be removed for each possible target.
  • We can calculate the total beans and use a prefix sum to determine the beans to be removed for each bag.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - we are using a constant amount of extra space.

Solution

To solve this problem, we can follow these steps:

  1. Sort the array of beans.
  2. Calculate the total number of beans.
  3. Iterate through the sorted array and for each unique number of beans at index i, calculate how many beans would need to be removed to make all the remaining bags equal to beans[i].
  4. Keep track of the minimum beans removed across all iterations.

We use sorting to facilitate the process of determining how many beans need to be removed for each potential target.

Code Solutions

def minimumBeansToRemove(beans):
    # Sort the beans array
    beans.sort()
    total_beans = sum(beans)
    n = len(beans)
    min_removal = float('inf')
    
    for i in range(n):
        # Calculate the number of beans to remove if we target beans[i]
        # Remaining non-empty bags would be n - i
        beans_to_remove = total_beans - beans[i] * (n - i)
        min_removal = min(min_removal, beans_to_remove)
    
    return min_removal
← Back to All Questions