🚀 Try This Problem First!

Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.

🔗 Problem Link: https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

Understanding the Problem

You are given an array of integers nums and an integer threshold. You must choose a positive integer divisor, divide every element of the array by it (rounding up to the nearest integer), sum all the results, and make sure that sum is ≤ threshold.

Goal: Find the smallest possible divisor that keeps the sum within the threshold.

Important detail — Ceiling Division: Every division rounds up, not down. So 7 ÷ 3 = 3 (not 2), and 10 ÷ 2 = 5.

Constraints:

1. 1 ≤ nums.length ≤ 5 × 10⁴
2. 1 ≤ nums[i] ≤ 10⁶
3. nums.length ≤ threshold ≤ 10⁶

Two Key Observations (Before Writing a Single Line of Code)

Minimum possible divisor: The divisor must be at least 1. Dividing by anything less than 1 isn't a positive integer. So:

low = 1

Maximum possible divisor: If divisor = max(nums), then every element divided by it gives at most 1 (due to ceiling), so the sum equals nums.length, which is always ≤ threshold (guaranteed by constraints). So:

high = max(nums)

Our answer lies in the range [1, max(nums)]. This is the search space for Binary Search.

Intuition — Why Binary Search?

Ask yourself: what happens as the divisor increases?

As divisor gets larger, each divided value gets smaller (or stays the same), so the total sum decreases or stays the same. This is a monotonic relationship — the green flag for Binary Search on the Answer.

Instead of trying every divisor from 1 to max(nums), we binary search over divisor values. For each candidate mid, we ask:

"Does dividing all elements by mid (ceiling) give a sum ≤ threshold?"

This feasibility check runs in O(N), making the whole approach O(N log(max(nums))).

The Feasibility Check — Ceiling Sum Simulation

Given a divisor mid, compute the sum of ⌈arr[i] / mid⌉ for all elements. If the total sum ≤ threshold, then mid is a valid divisor.

In Java, ceiling division of integers is done as:

Binary Search Strategy

1. If canDivide(mid) is true → mid might be the answer, but try smaller. Set ans = mid, high = mid - 1.
2. If canDivide(mid) is false → divisor is too small, increase it. Set low = mid + 1.

Dry Run — Example 1 (Step by Step)

Input: nums = [1, 2, 5, 9], threshold = 6

We start with low = 1 and high = 9 (max element in array).

Iteration 1: mid = 1 + (9 - 1) / 2 = 5

Compute ceiling sum with divisor 5: ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 5

5 ≤ 6 → ✅ Valid. Record ans = 5, search smaller → high = 4.

Iteration 2: mid = 1 + (4 - 1) / 2 = 2

Compute ceiling sum with divisor 2: ⌈1/2⌉ + ⌈2/2⌉ + ⌈5/2⌉ + ⌈9/2⌉ = 1 + 1 + 3 + 5 = 10

10 > 6 → ❌ Too large. Increase divisor → low = 3.

Iteration 3: mid = 3 + (4 - 3) / 2 = 3

Compute ceiling sum with divisor 3: ⌈1/3⌉ + ⌈2/3⌉ + ⌈5/3⌉ + ⌈9/3⌉ = 1 + 1 + 2 + 3 = 7

7 > 6 → ❌ Too large. Increase divisor → low = 4.

Iteration 4: mid = 4 + (4 - 4) / 2 = 4

Compute ceiling sum with divisor 4: ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 7

7 > 6 → ❌ Too large. Increase divisor → low = 5.

Loop ends: low (5) > high (4). Binary search terminates.

Output: ans = 5 ✅

The Code Implementation

Code Walkthrough — Step by Step

Setting bounds: We iterate through nums once to find max — this becomes our upper bound high. The lower bound low = 1 because divisors must be positive integers.

Binary Search loop: We pick mid = min + (max - min) / 2 as the candidate divisor. We check if using mid as the divisor keeps the ceiling sum ≤ threshold.

Feasibility helper (canDivide): For each element, we compute Math.ceil((double) arr[i] / mid) and accumulate the total. The cast to double is critical — without it, Java performs integer division (which truncates, not rounds up).

Narrowing the search: If the sum is within threshold → record ans = mid, try smaller (max = mid - 1). If the sum exceeds threshold → divisor is too small, increase it (min = mid + 1).

A Critical Bug to Watch Out For — The return min vs return ans Trap

In your original code, the final line was return min instead of return ans. This is a subtle bug. After the loop ends, min has overshot past the answer (it's now ans + 1). Always store the answer in a dedicated variable ans and return that. Using return min would return the wrong result in most cases.

Common Mistakes to Avoid

Wrong lower bound: Setting low = min(nums) instead of low = 1 seems intuitive but is wrong. A divisor smaller than the minimum element is still valid — for example, dividing [5, 9] by 3 gives ⌈5/3⌉ + ⌈9/3⌉ = 2 + 3 = 5, which could be within threshold.

Forgetting ceiling division: Using arr[i] / mid (integer division, which truncates) instead of Math.ceil((double) arr[i] / mid) is wrong. The problem explicitly states results are rounded up.

Returning min instead of ans: After the binary search loop ends, min > max, meaning min has already gone past the valid answer. Always return the stored ans.

Integer overflow in midpoint: Always use mid = min + (max - min) / 2 instead of (min + max) / 2. When both values are large (up to 10⁶), their sum can overflow an int.

Complexity Analysis

Time Complexity: O(N × log(max(nums)))

1. Binary search runs over [1, max(nums)] → at most log₂(10⁶) ≈ 20 iterations.
2. Each iteration calls canDivide which is O(N).
3. Total: O(N log M) where M = max(nums).

Space Complexity: O(1) No extra data structures — only a few integer variables are used throughout.

How This Relates to LeetCode 1011

This problem and LeetCode 1011 (Ship Packages Within D Days) are almost identical in structure:

🔗 LeetCode 1011 #

1. Search space: [max(weights), sum(weights)]
2. Feasibility check: Can we ship in ≤ D days?
3. Monotonic property: More capacity → fewer days
4. Goal: Minimize capacity

LeetCode 1283

1. Search space: [1, max(nums)]
2. Feasibility check: Is ceiling sum ≤ threshold?
3. Monotonic property: Larger divisor → smaller sum
4. Goal: Minimize divisor

Once you deeply understand one, the other takes minutes to solve.

Similar Problems (Same Pattern — Binary Search on Answer)

1. LeetCode 875 — Koko Eating Bananas [ Blog is also avaliable on this - Read Now ]
2. LeetCode 1011 — Capacity To Ship Packages Within D Days [ Blog is also avaliable on this - Read Now ]
3. LeetCode 410 — Split Array Largest Sum
4. LeetCode 2064 — Minimized Maximum of Products Distributed to Any Store

All follow the same template: identify a monotonic answer space, write an O(N) feasibility check, and binary search over it.

Key Takeaways

✅ When the problem asks "find the minimum value such that a condition holds" — think Binary Search on the Answer.

✅ The lower bound is the most constrained valid value (1 here, since divisors must be positive).

✅ The upper bound is the least constrained valid value (max element, guarantees sum = length ≤ threshold).

✅ Ceiling division in Java requires casting to double: Math.ceil((double) a / b).

✅ Always store the answer in a separate ans variable — never return min or max directly after a binary search loop.

Happy Coding! Smash that upvote if this helped you crack the pattern. 🚀