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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Removing Minimum Number of Magic Beans

Number: 2290

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given an array of positive integers representing the number of magic beans in each bag, remove any number of beans (possibly none) from each bag so that every non-empty bag (with at least one bean) has an equal number of beans. Determine the minimum number of beans that must be removed.

Key Insights

  • Consider each unique bean count as a potential target number that the non-empty bags should have.
  • Removing beans from bags with fewer beans than the target will remove all their beans (making them empty).
  • For bags with more beans than the target, remove just enough beans to reach the target.
  • Sorting the array helps in efficiently calculating the removal cost using a prefix sum array.
  • Iterate through each candidate target and use the prefix sum to quickly calculate the total removals required.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, plus O(n) for computing the prefix sum and iterating through candidates. Space Complexity: O(n) for the sorted array and prefix sum array.

Solution

The solution sorts the array and computes a prefix sum array to determine, for each candidate target value (taken from the sorted array), the cost of removing beans:

  1. For bags with counts less than the target, remove all beans.
  2. For bags with counts greater than or equal to the target, reduce them to the target count.
  3. Compute the removal cost using the prefix sum for efficiency.
  4. Return the minimum removal cost found.

This method leverages sorting and prefix sums to optimize the removal computation and avoid redundant calculations.

Code Solutions

# Function to calculate the minimum number of removals.
def minimum_removals(beans):
    # Sort the array for ordered processing.
    beans.sort()
    n = len(beans)
    # Compute prefix sums to quickly calculate removal costs.
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + beans[i]
    
    min_removals = float('inf')
    
    # Evaluate each bean count as a potential target.
    for i in range(n):
        # Remove all beans from bags with counts less than beans[i].
        removals_left = prefix[i]
        # For bags with counts >= beans[i], remove extra beans to reduce to beans[i].
        removals_right = (prefix[n] - prefix[i]) - (n - i) * beans[i]
        total_removals = removals_left + removals_right
        min_removals = min(min_removals, total_removals)
    
    return min_removals

# Example usage: Expected output 4.
print(minimum_removals([4,1,6,5]))
← Back to All Questions