DDSA Solutions

1760. Minimum Limit of Balls in a Bag

MediumView on LeetCode
ArrayBinary Search

Problem Overview

Minimize the maximum bag size after k operations (each op splits one bag).

Intuition

Minimize the maximum bag size after k operations (each op splits one bag). Binary search on max size.

Algorithm

  1. 1Binary search [1, max(nums)].
  2. 2Feasibility(maxSize): for each bag of size s, ops needed = ceil(s/maxSize)-1. Total ops <= maxOps.

Common Pitfalls

  • •ceil(s/maxSize)-1 = (s-1)/maxSize ops to split bag of size s into bags of maxSize.
1760.cs
C#
// Approach: Binary search on bag size; validate by counting required splits ≤ maxOperations.
// Time: O(n log(max)) Space: O(1)

public class Solution
{
    public int MinimumSize(int[] nums, int maxOperations)
    {
        int l = 1;
        int r = nums.Max();

        while (l < r)
        {
            int m = (l + r) / 2;
            if (NumOperations(nums, m) <= maxOperations)
                r = m;
            else
                l = m + 1;
        }

        return l;
    }

    // Returns the number of operations required to make m penalty.
    private int NumOperations(int[] nums, int m)
    {
        int operations = 0;
        foreach (int num in nums)
            operations += (num - 1) / m;
        return operations;
    }
}
Was this solution helpful?

Related Problems