Minimum Limit of Balls in a Bag - Practice Coding Problems

Minimum Limit of Balls in a Bag - Problem

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [9], maxOperations = 2

› Output: 3

💡 Note: Split bag of 9 balls: 9 → 6,3 → 3,3,3. Penalty is max(3,3,3) = 3.

Example 2 — Multiple Bags

$ Input: nums = [2,4,8,2], maxOperations = 4

› Output: 2

💡 Note: Split 8 into 4,4, then each 4 into 2,2. Result: [2,4,2,2,2,2,2]. Max penalty = 4, but we can do better by splitting the 4 too for penalty 2.

Example 3 — No Operations Needed

$ Input: nums = [1,2,3], maxOperations = 5

› Output: 3

💡 Note: Already optimal - max is 3 and we don't need any operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ maxOperations ≤ 10⁹
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of bag sizes and max operations allowed

Split Strategy

Binary search finds optimal penalty to target

Output

Minimum possible maximum bag size

Key Takeaway

🎯 Key Insight: Use binary search on the penalty value since the problem has monotonic property

Asked in

a Amazon 23 G Google 15 M Microsoft 12

The key insight is that this is a binary search on answer problem. If we can achieve penalty P with the given operations, we can also achieve any penalty > P. The optimal approach uses binary search to find the minimum achievable penalty. Time: O(n × log(max(nums))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n × log(max(nums)))	O(1)	Binary search on penalty values to find minimum achievable penalty efficiently
Linear Search on Answer	O(max(nums) × n)	O(1)	Try every possible penalty from 1 to max(nums) and check feasibility

Binary Search on Answer — Algorithm Steps

Step 1: Set search range [1, max(nums)]
Step 2: Binary search on penalty values
Step 3: For each mid, check if achievable with helper function
Step 4: Narrow search based on feasibility

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial range

Search between 1 and max(nums)

Check middle

Test if mid penalty is achievable

Narrow range

Continue until left==right

Code -

solution.c — C

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

int canAchievePenalty(int* nums, int numsSize, int penalty, int maxOperations) {
    long long operations = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > penalty) {
            operations += (nums[i] - 1) / penalty;
        }
    }
    return operations <= maxOperations;
}

int solution(int* nums, int numsSize, int maxOperations) {
    int left = 1;
    int right = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > right) {
            right = nums[i];
        }
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canAchievePenalty(nums, numsSize, mid, maxOperations)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[numsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int maxOperations;
    scanf("%d", &maxOperations);
    
    printf("%d\n", solution(nums, numsSize, maxOperations));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max(nums)))

Binary search log(max) iterations × checking all n bags

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

68.4K Views

Medium Frequency

~25 min Avg. Time

1.8K 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

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler