Binary Search on Answer Explained | Smallest Divisor Given a Threshold (LC 1283)

Binary Search on Answer – Smallest Divisor Given a Threshold

Binary Search on Answer is a powerful problem-solving pattern where instead of searching within an array, we perform binary search over the range of possible answers. LeetCode problem 1283 – Smallest Divisor Given a Threshold is a classic example of this pattern.

🔍 Problem Intuition

We are given an array of positive integers and a threshold. For any chosen divisor d, we divide each element by d, round it up using ceil, and sum the results.

Our goal is to find the smallest possible divisor such that this sum does not exceed the given threshold.

💡 Key Observation

• If the divisor is small → the sum becomes large
• If the divisor is large → the sum becomes small

This creates a monotonic condition, making it a perfect candidate for binary search on the answer.

⚠️ Important Edge Case

The divisor can never be 0. Starting binary search from 0 leads to division by zero. Hence, the search space must start from 1.

🧠 Approach

1. Search space: 1 to max(nums)
2. Check if a divisor satisfies the threshold condition
3. If valid, try smaller divisors (move left)
4. If invalid, increase the divisor (move right)

✅ Python Implementation

from math import ceil
class Solution:
    def condition(self, nums, mid, threshold):
        s = 0
        for i in nums:
            s += ceil(i / mid)
        return s <= threshold

    def smallestDivisor(self, nums, threshold):
        s = 1
        e = max(nums)

        while s < e:
            mid = (s + e) // 2
            if self.condition(nums, mid, threshold):
                e = mid
            else:
                s = mid + 1

        return s
  

⏱️ Complexity Analysis

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

📌 Why This Solution Is Optimal

A brute-force approach would check every possible divisor, which is inefficient. Binary Search on Answer reduces the problem drastically by leveraging the monotonic nature of the condition.

🔗 Source Code

Complete implementation is available here:
GitHub – LC1283 Python Solution

This problem is a great example of how understanding patterns can make seemingly hard problems straightforward and efficient.