1760. Minimum Limit of Balls in a Bag

Minimum Limit of Balls in a Bag (LeetCode 1760) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Answer / Condition Function subpattern.

How to solve Minimum Limit of Balls in a Bag

Minimum Limit of Balls in a Bag is a Binary Search on Answer Space problem, part of Binary Search Patterns. Learn binary search on answer space for optimization problems like Koko eating bananas and capacity to ship packages.

Work towards the solution in these steps:

1. Let's change the question if we know the maximum size of a bag what is the minimum number of bags you can make
2. note that as the maximum size increases the minimum number of bags decreases so we can binary search the maximum size

The reference solution runs in O(nlogn) time and O(1) space.

The Minimum Limit of Balls in a Bag solution and editorial walks through the full approach with reference code.

Problem statement

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.

Example 1:

Input: nums = [9], maxOperations = 2 Output: 3 Explanation: - Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3]. - Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3]. The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4 Output: 2 Explanation: - Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2]. The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.

Constraints:

- 1 <= nums.length <= 105

- 1 <= maxOperations, nums[i] <= 109

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Flipkart.

How to practise Minimum Limit of Balls in a Bag on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(1) space.

Open Minimum Limit of Balls in a Bag in the code editor, or read the Minimum Limit of Balls in a Bag editorial for a worked solution with its approach and complexity analysis.

Where Minimum Limit of Balls in a Bag sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Answer / Condition Function subpattern
• The full DSA patterns sheet

Problems related to Minimum Limit of Balls in a Bag

Other problems that use the same On Answer / Condition Function and Binary Search Patterns techniques:

• Capacity To Ship Packages Within D Days — Medium, same subpattern
• Koko Eating Bananas — Medium, same subpattern
• Maximum Candies Allocated to K Children — Medium, same subpattern
• Minimized Maximum of Products Distributed to Any Store — Medium, same subpattern
• Minimize Max Distance to Gas Station — Hard, same subpattern
• Minimum Number of Days to Make m Bouquets — Medium, same subpattern

Minimum Limit of Balls in a Bag FAQ