Find the Smallest Divisor

📋

Problem

Imagine you have a list of package weights and want to find the smallest box size that can ship all packages without exceeding a given total shipping time.

Given an array of integers nums and an integer threshold, find the smallest divisor such that the sum of each element in nums divided by the divisor (rounded up) is less than or equal to threshold. Return this smallest divisor.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^6nums.length ≤ threshold ≤ 10^6

Edge cases: All elements are 1 and threshold equals length → smallest divisor is 1Threshold equals length → divisor must be at least max elementThreshold is very large → smallest divisor can be 1

</>

IDE

def smallest_divisor(nums: list[int], threshold: int) -> int:public int smallestDivisor(int[] nums, int threshold)int smallestDivisor(vector<int>& nums, int threshold)function smallestDivisor(nums, threshold)

def smallest_divisor(nums, threshold):
    # Write your solution here
    pass

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int smallestDivisor(vector<int>& nums, int threshold) {
    // Write your solution here
    return 0;
}

function smallestDivisor(nums, threshold) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: max(nums)Greedy approach returning max element as divisor without checking smaller divisors.✅ Implement binary search over divisor range with feasibility function to find minimal divisor.

Wrong: 1Ignoring threshold constraints and always returning 1 as divisor.✅ Check feasibility function sums and increase divisor if sum exceeds threshold.

Wrong: Incorrect divisor due to off-by-one errorBinary search mid calculation or boundary updates are incorrect.✅ Use mid = left + (right - left) // 2 and update left/right boundaries properly.

Wrong: Crash or invalid output on empty inputNo handling for empty nums array.✅ Add explicit check for empty input and return 1.

Wrong: Wrong divisor due to confusing problem with knapsackApplying knapsack or subset sum logic instead of binary search on answer space.✅ Use binary search with feasibility function summing ceil divisions.

✓

Test Cases

Focus on handling edge cases like empty input and single elements correctly.

Watch out for common algorithmic traps like greedy approaches and off-by-one errors.

Optimize your solution to binary search on answer space to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,2,5,9],"threshold":6}

Expected5

⏱ Performance - must finish in 2000ms

Dividing by 5 gives sums: ceil(1/5)=1, ceil(2/5)=1, ceil(5/5)=1, ceil(9/5)=2; total = 5 ≤ 6. Dividing by 4 would give total 7 > 6, so 5 is smallest.

💡 Consider binary searching the divisor between 1 and max(nums).

💡 Use a feasibility function to check if a divisor yields sum ≤ threshold.

💡 Return the smallest divisor for which the feasibility function is true.

Why it failed: Returned divisor too small or too large due to incorrect feasibility check or binary search bounds. Fix by correctly implementing feasibility function using ceil division and adjusting binary search boundaries.

✓ Correctly finds smallest divisor using binary search and feasibility function.

t1_02basic

Input{"nums":[2,3,5,7,11],"threshold":11}

Expected3

⏱ Performance - must finish in 2000ms

Dividing by 3 yields sums: ceil(2/3)=1, ceil(3/3)=1, ceil(5/3)=2, ceil(7/3)=3, ceil(11/3)=4; total=11 ≤ threshold. Dividing by 2 yields total 17 > 11, so 3 is smallest.

💡 Check sums of ceil divisions for candidate divisors.

💡 Binary search between 1 and max(nums) to find minimal divisor.

💡 Stop when feasibility function first returns true.

Why it failed: Incorrect sum calculation or binary search off-by-one error caused wrong divisor. Fix by using math.ceil or equivalent integer division and adjusting binary search mid calculation.

✓ Correctly identifies smallest divisor with binary search and feasibility check.

t2_01edge

Input{"nums":[],"threshold":0}

Expected1

⏱ Performance - must finish in 2000ms

Empty array means sum is 0 for any divisor; smallest divisor is 1 by definition.

💡 Consider what happens when nums is empty.

💡 Sum of ceil divisions is zero regardless of divisor.

💡 Return 1 as smallest divisor since no elements to divide.

Why it failed: Code crashes or returns invalid divisor on empty input. Fix by handling empty nums case explicitly, returning 1.

✓ Handles empty input correctly by returning 1.

t2_02edge

Input{"nums":[10],"threshold":3}

Expected4

⏱ Performance - must finish in 2000ms

Single element 10 divided by divisor d must satisfy ceil(10/d) ≤ 3. Smallest d is 4 since ceil(10/4)=3.

💡 For single element, divisor must be at least ceil(nums[0]/threshold).

💡 Check feasibility function for single element arrays.

💡 Return smallest divisor satisfying ceil division ≤ threshold.

Why it failed: Fails single element case by not computing ceil division correctly. Fix by using ceil division for single element and returning correct divisor.

✓ Correctly handles single element input.

t2_03edge

Input{"nums":[1,1,1,1],"threshold":4}

Expected1

⏱ Performance - must finish in 2000ms

All elements are 1 and threshold equals length; smallest divisor is 1 since sum of ceil divisions is 4.

💡 When all elements are 1, smallest divisor is 1 if threshold ≥ length.

💡 Sum of ceil divisions equals length for divisor=1.

💡 Check feasibility function returns true for divisor=1.

Why it failed: Fails to handle all ones array correctly, returning divisor > 1. Fix by ensuring feasibility function correctly sums ceil divisions for divisor=1.

✓ Correctly returns 1 for all ones array with threshold equal to length.

t3_01corner

Input{"nums":[1,2,3,4,5],"threshold":5}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach picking divisor as max(nums) fails; smallest divisor is 5 because sum ceil divisions with divisor=5 is 5 ≤ threshold.

💡 Greedy picking max(nums) as divisor may not always be minimal.

💡 Use binary search to find smallest divisor that satisfies sum ≤ threshold.

💡 Check feasibility function for divisors less than max(nums).

Why it failed: Greedy approach returns max(nums) without checking smaller divisors. Fix by implementing binary search over divisor range.

✓ Correctly avoids greedy trap by binary searching answer space.

t3_02corner

Input{"nums":[100,200,300],"threshold":100}

Expected6

⏱ Performance - must finish in 2000ms

Confusing 0/1 knapsack with this problem leads to wrong divisor; smallest divisor is 6 since sum ceil divisions with 6 is 100.

💡 This problem requires binary search on divisor, not knapsack DP.

💡 Use feasibility function summing ceil divisions to check divisor.

💡 Avoid confusing problem with subset sum or knapsack variants.

Why it failed: Mistakenly applying knapsack or subset sum logic leads to wrong divisor. Fix by using binary search with feasibility function summing ceil divisions.

✓ Correctly applies binary search on answer space, not knapsack.

t3_03corner

Input{"nums":[10,10,10],"threshold":5}

Expected6

⏱ Performance - must finish in 2000ms

Off-by-one error in binary search mid calculation causes wrong divisor; correct smallest divisor is 6.

💡 Check binary search mid calculation and loop conditions carefully.

💡 Ensure feasibility function is called with correct divisor values.

💡 Adjust binary search boundaries to avoid infinite loops or off-by-one errors.

Why it failed: Off-by-one error in binary search causes incorrect divisor. Fix by using mid = left + (right - left) // 2 and updating boundaries correctly.

✓ Binary search implemented with correct mid and boundary updates.

t4_01performance

Input{"nums":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901,999900],"threshold":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and max nums near 10^6; O(n log(max(nums))) solution must complete within 2 seconds.

💡 Binary search on divisor reduces search space from max(nums) to log(max(nums)).

💡 Feasibility function runs in O(n) time per check.

💡 Overall complexity O(n log(max(nums))) is efficient for n=100.

Why it failed: Brute force linear search over divisor causes TLE. Fix by implementing binary search on answer space with feasibility function.

✓ Efficient binary search solution runs within time limits.

Practice

1. You are given a sorted array and a target value. You need to find the starting and ending indices of the target value in the array. Which algorithmic approach guarantees an optimal solution with logarithmic time complexity?

easy

A. Linear scan from start to end to find first and last occurrences

B. Greedy approach to jump to target positions based on value comparisons

C. Modified binary search to find leftmost and rightmost positions separately

D. Dynamic programming to store intermediate results for each index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find target positions efficiently.

2. Step 2: Identify suitable algorithm

   Modified binary search can find leftmost and rightmost indices in O(log n) time, which is optimal compared to linear scan or greedy methods.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted property for O(log n) search [OK]

Hint: Sorted array + position search -> modified binary search [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Confusing greedy with binary search
• Using DP unnecessarily

2. You are given a sorted array where every element appears exactly twice except for one element which appears only once. Which algorithmic approach guarantees an optimal O(log n) time solution to find the single element?

easy

A. Modified binary search using index parity to halve the search space

B. Dynamic programming to store counts of elements and find the unique one

C. Linear scan checking pairs sequentially until the unique element is found

D. Greedy approach selecting elements based on local pair matches

Solution

1. Step 1: Understand problem constraints

   The array is sorted and every element except one appears twice consecutively.

2. Step 2: Identify algorithm that exploits sorted pairs

   Modified binary search using index parity halves the search space by comparing pairs, achieving O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search with parity is known optimal for this problem [OK]

Hint: Use parity-based binary search for O(log n) solution [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Using DP unnecessarily
• Applying greedy without global insight

3. Consider the following Python code implementing the optimal solution for splitting an array into m subarrays minimizing the largest sum. Given nums = [7, 2, 5, 10] and m = 2, what is the final returned value?

easy

A. 10

B. 12

C. 17

D. 15

Solution

1. Step 1: Calculate prefix sums

   prefix = [0, 7, 9, 14, 24]

2. Step 2: Binary search on answer space [7,24]

   Check mid=15: can split into subarrays with max sum ≤15? Yes (e.g., [7,2,5] and [10]). Try lower mid=11: cannot split into 2 subarrays with max sum ≤11. Finally, minimal largest sum found is 12.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal largest sum for splitting [7,2,5,10] into 2 parts is 12 [OK]

Hint: Trace binary search mid and feasibility check carefully [OK]

Common Mistakes:

• Off-by-one in bisect leading to wrong subarray boundaries
• Confusing max element with sum for low/high bounds
• Miscounting number of splits in feasibility check

4. Examine the following code snippet intended to search a target in a 2D matrix using binary search treating it as a 1D array. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.

medium

A. Line 6: row, col = divmod(mid, n)

B. Line 3: left, right = 0, m * n - 1

C. Line 1: m, n = len(matrix), len(matrix[0])

D. Line 9: left = mid + 1

Solution

1. Step 1: Check for empty matrix handling

   The code does not check if matrix or matrix[0] is empty before accessing len(matrix[0]), which can cause runtime errors.

2. Step 2: Verify other lines

   Lines for binary search boundaries and index mapping are correct assuming valid input.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing empty matrix check leads to crash [OK]

Hint: Always check for empty matrix or empty rows before accessing indices [OK]

Common Mistakes:

• Forgetting empty input checks
• Incorrect index mapping
• Wrong boundary updates

5. What is the time complexity of the recursive binary search algorithm used to find the insert position in a sorted array of size n?

medium

A. O(n)

B. O(log n) time but O(n) space due to recursion stack

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify the number of recursive calls

   Each call halves the search space, so number of calls is O(log n).

2. Step 2: Analyze space usage

   Recursion stack depth is O(log n), but question asks for time complexity only.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search time complexity is logarithmic [OK]

Hint: Binary search halves input each step -> O(log n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time complexity
• Assuming linear time due to recursion
• Mistaking O(n log n) from sorting algorithms