Removing Minimum Number of Magic Beans - Practice Coding Problems

Removing Minimum Number of Magic Beans - Problem

Array Greedy Sorting Enumeration Prefix Sum Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: beans = [4,1,6,5]

› Output: 4

💡 Note: Remove 1 bean from bag with 1 bean (empty it), remove 2 beans from bag with 6 beans (keep 4), remove 1 bean from bag with 5 beans (keep 4). All remaining bags have 4 beans each. Total removals = 1 + 2 + 1 = 4.

Example 2 — All Same Target

$ Input: beans = [2,10,3,2]

› Output: 7

💡 Note: Set target to 2: empty bag with 2 beans (0 removals each), remove 8 from bag with 10 beans, remove 1 from bag with 3 beans. Total = 0 + 0 + 8 + 1 = 9. But target=2 is better: total removals = 7.

Example 3 — Single Element

$ Input: beans = [5]

› Output: 0

💡 Note: Only one bag, keep it as is. No removals needed.

Constraints

1 ≤ beans.length ≤ 10⁵
1 ≤ beans[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of bag sizes: [4, 1, 6, 5]

Process

Try each value as target level, calculate removals needed

Output

Minimum removals needed: 4 (target level = 4)

Key Takeaway

🎯 Key Insight: Only existing array values can be optimal target levels - sort first then use prefix sums for O(n log n) solution

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that only existing values in the array can be optimal targets. After sorting, we can use prefix sums to calculate removals efficiently: remove all beans from smaller bags + reduce larger bags to target level. Best approach is prefix sum optimization with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possible Targets	O(n × max(beans))	O(1)	Try every possible target value from 1 to max(beans)
Optimized with Prefix Sums	O(n log n)	O(1)	Use prefix sums to calculate removals in O(1) per target
Sort + Try Each Value	O(n²)	O(1)	Sort array first, then only try existing values as targets

Brute Force - Try All Possible Targets — Algorithm Steps

Iterate through all possible target values from 1 to max(beans)
For each target, calculate total removals needed
Return minimum removals found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Target=2

Calculate removals for each bag if target is 2

Try Target=3

Calculate removals for each bag if target is 3

Find Minimum

Return the target that requires fewest removals

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* beans, int n) {
    if (n == 0) return 0;
    
    long long totalBeans = 0;
    int maxBeans = 0;
    for (int i = 0; i < n; i++) {
        totalBeans += beans[i];
        if (beans[i] > maxBeans) {
            maxBeans = beans[i];
        }
    }
    
    long long minRemovals = LLONG_MAX;
    
    // Try all possible target values from 1 to max(beans)
    for (int target = 1; target <= maxBeans; target++) {
        long long removals = 0;
        int remainingBags = 0;
        
        for (int i = 0; i < n; i++) {
            if (beans[i] >= target) {
                // Keep this bag with target beans
                removals += beans[i] - target;
                remainingBags++;
            } else {
                // Remove all beans from this bag
                removals += beans[i];
            }
        }
        
        // Only consider if at least one bag remains
        if (remainingBags > 0) {
            if (removals < minRemovals) {
                minRemovals = removals;
            }
        }
    }
    
    return minRemovals == LLONG_MAX ? totalBeans : minRemovals;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int beans[10000];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            beans[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    long long result = solution(beans, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × max(beans))

For each of max(beans) possible targets, we scan the array of n elements

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculation, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possible Targets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler