1760.Minimum Limit of Balls in a Bag.md

Difficulty	Source	Tags
Medium	Daily Question (POTD 07-Dec)	Binary Search Array

🚀 1760 - Minimum Limit of Balls in a Bag 🧠

Problem Link:

LeetCode - Minimum Limit of Balls in a Bag

💡 Problem Breakdown:

You are tasked to minimize the maximum number of balls in a bag after performing at most maxOperations. Each operation allows dividing a bag of balls into two smaller bags. Here's how we break down the problem:

1. The goal is to minimize the "penalty," which is the largest number of balls in any bag after performing all operations.
2. The problem can be approached by evaluating whether a specific penalty value is achievable using the available operations.

🔍 Example Walkthrough:

Example 1:

Input:
nums = [9], maxOperations = 2

Output:
3

Explanation:

• Start with one bag: [9].
• Operation 1: Divide 9 into 6 and 3 → [6, 3].
• Operation 2: Divide 6 into 3 and 3 → [3, 3, 3].

Now, the largest bag contains 3 balls, so the penalty is 3.

Example 2:

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

Output:
2

Explanation:

• Start with bags [2, 4, 8, 2].
• Operation 1: Divide 8 into 4 and 4 → [2, 4, 4, 4, 2].
• Operation 2: Divide one 4 into 2 and 2 → [2, 2, 4, 4, 2, 2].
• Operation 3: Divide another 4 into 2 and 2 → [2, 2, 2, 4, 2, 2, 2].
• Operation 4: Divide the last 4 into 2 and 2 → [2, 2, 2, 2, 2, 2, 2].

Now, the largest bag contains 2 balls, so the penalty is 2.

Constraints:

• $1 \leq nums.length \leq 10^5$
• $1 \leq maxOperations, nums[i] \leq 10^9$

🎯 My Approach:

To minimize the penalty, we use binary search combined with a greedy check:

1. Binary Search:

   • Search the penalty in the range [1, max(nums)].
   • Midpoint (mid) of the search range represents a candidate penalty.

2. Feasibility Check:

   • For each bag in nums, calculate how many splits are needed to make all resulting bags ≤ mid.
   • Sum the operations required for all bags.
   • If the total number of operations ≤ maxOperations, the candidate penalty is feasible.

3. Update Search Range:

   • If feasible, try a smaller penalty (right = mid - 1).
   • If not feasible, increase the penalty (left = mid + 1).

🕒 Time Complexity:

• Time Complexity:
  $O(n \log(max(nums)))$

  • O(\log(max(nums))) for binary search.
  • O(n) to evaluate feasibility for each candidate penalty.

• Space Complexity:
  $O(1)$: No additional space beyond the input.

📝 Solution Code

Code (C):

bool canDivide(int* nums, int numsSize, int maxSize, int maxOperations) {
    int operations = 0;
    for (int i = 0; i < numsSize; i++) {
        operations += (nums[i] - 1) / maxSize;
        if (operations > maxOperations) return false;
    }
    return true;
}

int minimumSize(int* nums, int numsSize, int maxOperations) {
    int left = 1, right = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > right) right = nums[i];
    }

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canDivide(nums, numsSize, mid, maxOperations)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Code (C++)

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());

        while (left < right) {
            int mid = left + (right - left) / 2;
            int operations = 0;

            for (int num : nums) {
                operations += (num - 1) / mid;
                if (operations > maxOperations) {
                    left = mid + 1;
                    goto nextIteration; 
                }
            }
            right = mid;

        nextIteration:;
        }
        return left;
    }
};

Code (Java)

class Solution {
    private boolean canDivide(int[] nums, int maxSize, int maxOperations) {
        int operations = 0;
        for (int num : nums) {
            operations += (num - 1) / maxSize;
            if (operations > maxOperations) return false;
        }
        return true;
    }

    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = Integer.MIN_VALUE;
        for (int num : nums) {
            right = Math.max(right, num);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canDivide(nums, mid, maxOperations)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

Code (Python)

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def canDivide(maxSize: int) -> bool:
            return sum((num - 1) // maxSize for num in nums) <= maxOperations

        left, right = 1, max(nums)
        while left < right:
            mid = left + (right - left) // 2
            if canDivide(mid):
                right = mid  
            else:
                left = mid + 1  
        return left

Code (Rust)

impl Solution {
    pub fn minimum_size(nums: Vec<i32>, max_operations: i32) -> i32 {
        fn can_divide(nums: &Vec<i32>, max_size: i32, max_operations: i32) -> bool {
            nums.iter()
                .map(|&num| (num - 1) / max_size)
                .sum::<i32>() <= max_operations
        }

        let (mut left, mut right) = (1, *nums.iter().max().unwrap());

        while left < right {
            let mid = left + (right - left) / 2;
            if can_divide(&nums, mid, max_operations) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        left
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!