LeetCode 1760 Explained: Binary Search on Answer with Clear possible() Function Intuition

LeetCode 1760: Minimum Limit of Balls in a Bag (Binary Search on Answer)

LeetCode 1760 is a classic example of the Binary Search on Answer pattern. While many tutorials explain the binary search part, they often skip the most important piece — how the feasibility (possible) function actually works.

In this article, we will focus on building the intuition behind the solution, especially the logic used to count operations inside the possible() function.

---

🔹 Problem Overview

You are given an array nums where each element represents the number of balls in a bag. You are allowed to perform at most maxOperations operations.

In one operation, you can split a bag into two bags with any positive number of balls. Your goal is to minimize the maximum number of balls in any bag.

---

🔹 Why Binary Search Works Here

We are not searching inside the array. Instead, we are searching for the minimum possible maximum value after all allowed operations.

The answer range is clearly bounded:

• Minimum possible value → 1
• Maximum possible value → max(nums)

Since the feasibility of a value is monotonic (if a value works, all larger values work), binary search is the optimal approach.

---

🔹 What Does mid Represent?

During binary search, mid represents a candidate answer:

Can we make every bag have at most mid balls using at most maxOperations splits?

This turns the problem into a simple YES / NO decision — perfect for binary search.

---

🔹 Understanding the possible() Function

This is the most important part of the solution. For each bag with i balls, we calculate how many operations are required to ensure that no resulting bag exceeds mid.

The formula used is:

operations += ceil(i / mid) - 1
  

Why This Works

If a bag has i balls and we want each part to be at most mid, we need:

• ceil(i / mid) total pieces
• Number of operations = pieces − 1

The subtraction of 1 is crucial. Even when a value is perfectly divisible, counting pieces directly would overestimate the number of operations.

---

🔹 Early Stopping Optimization

If at any point the required operations exceed maxOperations, we immediately return false.

This keeps the algorithm efficient and avoids unnecessary computation.

---

🔹 Complete Python Solution

from math import ceil

class Solution:
    def possible(self, nums, maxOperations, mid):
        opr = 0
        for i in nums:
            opr += ceil(i / mid) - 1
            if opr > maxOperations:
                return False
        return True

    def minimumSize(self, nums, maxOperations):
        s = 1
        l = max(nums)

        while s < l:
            mid = (s + l) // 2
            if self.possible(nums, maxOperations, mid):
                l = mid
            else:
                s = mid + 1

        return s
  

---

🔹 Time and Space Complexity

• Time Complexity: O(n log max(nums))
• Space Complexity: O(1)

---

🔹 Final Takeaway

This problem is not just about binary search — it is about correctly modeling the number of operations required to enforce a constraint.

Once you understand how ceil(i / mid) - 1 works, this entire class of problems becomes much easier to solve.

This same pattern appears in many interview problems where the goal is to minimize a maximum value under limited operations.

🔗 Full source code available here: GitHub – LeetCode 1760 Solution