Find the Smallest Divisor

🎯

Find the Smallest Divisor

mediumBINARY_SEARCHAmazonGoogle

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.

💡 This problem asks you to find a minimum divisor such that when dividing each number in an array and summing the results (rounded up), the total does not exceed a threshold. Beginners often struggle because the answer is not found by searching the array directly but by searching the space of possible divisors, which requires a modified binary search approach.

📋

Problem Statement

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

💡

Example

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

Output5

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.

• All elements are 1 and threshold equals length → smallest divisor is 1
• Threshold equals length → divisor must be at least max element
• Threshold is very large → smallest divisor can be 1
• Array has one element → divisor is ceil(nums[0]/threshold)

⚠️

Common Mistakes

Using integer division instead of ceiling division

Sum underestimates, leading to incorrect divisor

✅ Use (num + divisor - 1) // divisor or math.ceil(num / divisor)

Setting binary search boundaries incorrectly

Infinite loop or missing correct divisor

✅ Set low = 1 and high = max(nums) properly

Not handling early exit in feasibility check

Unnecessary computation, slower runtime

✅ Return false immediately when sum exceeds threshold

Not testing edge cases like single element or threshold equals array length

Code may fail or produce wrong output on edge inputs

✅ Add tests and handle these cases explicitly if needed

🧠

Brute Force (Linear Search on Divisor)

💡 This approach tries every possible divisor from 1 up to the maximum element in the array. It is simple and helps understand the problem but is inefficient for large inputs.

Intuition

Try every divisor starting from 1 upwards, compute the sum of ceil divisions, and check if it meets the threshold. The first divisor that satisfies the condition is the answer.

Algorithm

1. Find the maximum number in nums as the upper bound for divisor.
2. For each divisor from 1 to max_num:
3. Calculate the sum of ceil(nums[i] / divisor) for all elements.
4. If sum ≤ threshold, return the current divisor.

💡 The algorithm is straightforward but inefficient because it checks all divisors without pruning.

</>

Code

import math

def smallest_divisor(nums, threshold):
    max_num = max(nums)
    for divisor in range(1, max_num + 1):
        total = 0
        for num in nums:
            total += math.ceil(num / divisor)
        if total <= threshold:
            return divisor

# Driver code
if __name__ == "__main__":
    nums = [1, 2, 5, 9]
    threshold = 6
    print(smallest_divisor(nums, threshold))  # Output: 5

Line Notes

max_num = max(nums)Finds the maximum element to set the upper bound for divisor search

for divisor in range(1, max_num + 1)Iterates over all possible divisors from smallest to largest

total += math.ceil(num / divisor)Calculates the rounded-up division for each element

if total <= thresholdChecks if current divisor satisfies the threshold condition

import java.util.*;

public class SmallestDivisor {
    public static int smallestDivisor(int[] nums, int threshold) {
        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }
        for (int divisor = 1; divisor <= maxNum; divisor++) {
            int total = 0;
            for (int num : nums) {
                total += (num + divisor - 1) / divisor; // ceil division
            }
            if (total <= threshold) {
                return divisor;
            }
        }
        return maxNum; // fallback
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9};
        int threshold = 6;
        System.out.println(smallestDivisor(nums, threshold)); // Output: 5
    }
}

Line Notes

int maxNum = 0;Initialize maxNum to find the maximum element

maxNum = Math.max(maxNum, num);Update maxNum with the largest element found

total += (num + divisor - 1) / divisor;Performs ceiling division without floating point

if (total <= threshold)Checks if current divisor meets the threshold condition

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int smallestDivisor(vector<int>& nums, int threshold) {
    int maxNum = *max_element(nums.begin(), nums.end());
    for (int divisor = 1; divisor <= maxNum; divisor++) {
        int total = 0;
        for (int num : nums) {
            total += (num + divisor - 1) / divisor; // ceil division
        }
        if (total <= threshold) {
            return divisor;
        }
    }
    return maxNum; // fallback
}

int main() {
    vector<int> nums = {1, 2, 5, 9};
    int threshold = 6;
    cout << smallestDivisor(nums, threshold) << endl; // Output: 5
    return 0;
}

Line Notes

int maxNum = *max_element(nums.begin(), nums.end());Finds the maximum element in nums

for (int divisor = 1; divisor <= maxNum; divisor++)Checks all possible divisors from 1 to maxNum

total += (num + divisor - 1) / divisor;Computes ceil division using integer arithmetic

if (total <= threshold)Returns divisor if sum meets threshold

function smallestDivisor(nums, threshold) {
    const maxNum = Math.max(...nums);
    for (let divisor = 1; divisor <= maxNum; divisor++) {
        let total = 0;
        for (const num of nums) {
            total += Math.floor((num + divisor - 1) / divisor); // ceil division
        }
        if (total <= threshold) {
            return divisor;
        }
    }
    return maxNum; // fallback
}

// Test
console.log(smallestDivisor([1, 2, 5, 9], 6)); // Output: 5

Line Notes

const maxNum = Math.max(...nums);Finds the maximum element to limit divisor search

for (let divisor = 1; divisor <= maxNum; divisor++)Iterates over all possible divisors

total += Math.floor((num + divisor - 1) / divisor);Performs ceiling division using integer math

if (total <= threshold)Checks if current divisor satisfies the threshold

⏱

Complexity

TimeO(n * max(nums))

SpaceO(1)

For each divisor from 1 to max element, we sum over n elements, resulting in O(n * max(nums)) time.

💡 If max(nums) is 10^6 and n is 10^5, this means 10^11 operations, which is too large for practical use.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimization.

🧠

Binary Search on Divisor (Answer Space)

💡 Instead of checking every divisor, we use binary search on the range of possible divisors to efficiently find the smallest valid one.

Intuition

The sum of ceil divisions decreases as divisor increases, so the feasibility function is monotonic. We can binary search the divisor space to find the smallest divisor that meets the threshold.

Algorithm

1. Set low = 1 and high = max(nums).
2. While low < high:
3. mid = (low + high) // 2
4. Calculate sum of ceil(nums[i] / mid).
5. If sum > threshold, set low = mid + 1; else high = mid.
6. Return low as the smallest divisor.

💡 The key is recognizing the monotonic relationship and using binary search to reduce time complexity.

</>

Code

import math

def smallest_divisor(nums, threshold):
    low, high = 1, max(nums)
    while low < high:
        mid = (low + high) // 2
        total = 0
        for num in nums:
            total += math.ceil(num / mid)
        if total > threshold:
            low = mid + 1
        else:
            high = mid
    return low

# Driver code
if __name__ == "__main__":
    nums = [1, 2, 5, 9]
    threshold = 6
    print(smallest_divisor(nums, threshold))  # Output: 5

Line Notes

low, high = 1, max(nums)Initialize search boundaries for divisor

while low < high:Loop until search space is narrowed to one element

total += math.ceil(num / mid)Calculate sum of ceil divisions for current mid divisor

if total > threshold:If sum too large, need bigger divisor to reduce sum

import java.util.*;

public class SmallestDivisor {
    public static int smallestDivisor(int[] nums, int threshold) {
        int low = 1, high = 0;
        for (int num : nums) {
            high = Math.max(high, num);
        }
        while (low < high) {
            int mid = low + (high - low) / 2;
            int total = 0;
            for (int num : nums) {
                total += (num + mid - 1) / mid;
            }
            if (total > threshold) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9};
        int threshold = 6;
        System.out.println(smallestDivisor(nums, threshold)); // Output: 5
    }
}

Line Notes

int low = 1, high = 0;Initialize binary search bounds

high = Math.max(high, num);Find maximum element for upper bound

total += (num + mid - 1) / mid;Ceiling division without floating point

if (total > threshold)Adjust search space based on feasibility

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int smallestDivisor(vector<int>& nums, int threshold) {
    int low = 1, high = *max_element(nums.begin(), nums.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        int total = 0;
        for (int num : nums) {
            total += (num + mid - 1) / mid; // ceil division
        }
        if (total > threshold) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<int> nums = {1, 2, 5, 9};
    int threshold = 6;
    cout << smallestDivisor(nums, threshold) << endl; // Output: 5
    return 0;
}

Line Notes

int low = 1, high = *max_element(nums.begin(), nums.end());Set binary search boundaries

while (low < high)Loop until search space is reduced to one

total += (num + mid - 1) / mid;Calculate sum with ceiling division

if (total > threshold)If sum too large, increase divisor

function smallestDivisor(nums, threshold) {
    let low = 1, high = Math.max(...nums);
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        let total = 0;
        for (const num of nums) {
            total += Math.floor((num + mid - 1) / mid); // ceil division
        }
        if (total > threshold) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
console.log(smallestDivisor([1, 2, 5, 9], 6)); // Output: 5

Line Notes

let low = 1, high = Math.max(...nums);Initialize binary search range

while (low < high)Continue until search space is one element

total += Math.floor((num + mid - 1) / mid);Ceiling division using integer math

if (total > threshold)Adjust low bound if sum exceeds threshold

⏱

Complexity

TimeO(n log(max(nums)))

SpaceO(1)

Binary search runs in log(max(nums)) steps, each step sums over n elements, total O(n log(max(nums))).

💡 For n=10^5 and max(nums)=10^6, this is about 10^5 * 20 = 2 million operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, making it the preferred solution in interviews.

🧠

Binary Search with Helper Feasibility Function

💡 This approach separates the feasibility check into a helper function for cleaner code and better readability, which is a good practice in interviews.

Intuition

Use a helper function to check if a given divisor satisfies the threshold condition, then binary search over divisors using this helper.

Algorithm

1. Define a helper function that returns true if sum of ceil(nums[i]/divisor) ≤ threshold.
2. Initialize low = 1 and high = max(nums).
3. While low < high:
4. mid = (low + high) // 2
5. Use helper to check feasibility with mid.
6. If feasible, set high = mid; else low = mid + 1.
7. Return low.

💡 Modularizing feasibility makes the binary search logic clearer and easier to debug.

</>

Code

import math

def is_feasible(nums, divisor, threshold):
    total = 0
    for num in nums:
        total += math.ceil(num / divisor)
        if total > threshold:
            return False
    return True

def smallest_divisor(nums, threshold):
    low, high = 1, max(nums)
    while low < high:
        mid = (low + high) // 2
        if is_feasible(nums, mid, threshold):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == "__main__":
    nums = [1, 2, 5, 9]
    threshold = 6
    print(smallest_divisor(nums, threshold))  # Output: 5

Line Notes

def is_feasible(nums, divisor, threshold):Defines a helper to check if divisor meets threshold

if total > threshold:Early exit to improve efficiency when sum exceeds threshold

if is_feasible(nums, mid, threshold):Uses helper to decide binary search direction

low, high = 1, max(nums)Initialize binary search bounds

import java.util.*;

public class SmallestDivisor {
    private static boolean isFeasible(int[] nums, int divisor, int threshold) {
        int total = 0;
        for (int num : nums) {
            total += (num + divisor - 1) / divisor;
            if (total > threshold) {
                return false;
            }
        }
        return true;
    }

    public static int smallestDivisor(int[] nums, int threshold) {
        int low = 1, high = 0;
        for (int num : nums) {
            high = Math.max(high, num);
        }
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (isFeasible(nums, mid, threshold)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9};
        int threshold = 6;
        System.out.println(smallestDivisor(nums, threshold)); // Output: 5
    }
}

Line Notes

private static boolean isFeasible(int[] nums, int divisor, int threshold)Helper method to check feasibility

if (total > threshold)Early return to avoid unnecessary computation

if (isFeasible(nums, mid, threshold))Binary search decision based on helper result

int low = 1, high = 0;Initialize binary search bounds

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool isFeasible(const vector<int>& nums, int divisor, int threshold) {
    int total = 0;
    for (int num : nums) {
        total += (num + divisor - 1) / divisor;
        if (total > threshold) {
            return false;
        }
    }
    return true;
}

int smallestDivisor(vector<int>& nums, int threshold) {
    int low = 1, high = *max_element(nums.begin(), nums.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (isFeasible(nums, mid, threshold)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    vector<int> nums = {1, 2, 5, 9};
    int threshold = 6;
    cout << smallestDivisor(nums, threshold) << endl; // Output: 5
    return 0;
}

Line Notes

bool isFeasible(const vector<int>& nums, int divisor, int threshold)Helper function to check feasibility

if (total > threshold)Early exit to improve performance

if (isFeasible(nums, mid, threshold))Binary search uses helper to decide direction

int low = 1, high = *max_element(nums.begin(), nums.end());Initialize binary search range

function isFeasible(nums, divisor, threshold) {
    let total = 0;
    for (const num of nums) {
        total += Math.floor((num + divisor - 1) / divisor);
        if (total > threshold) {
            return false;
        }
    }
    return true;
}

function smallestDivisor(nums, threshold) {
    let low = 1, high = Math.max(...nums);
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (isFeasible(nums, mid, threshold)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Test
console.log(smallestDivisor([1, 2, 5, 9], 6)); // Output: 5

Line Notes

function isFeasible(nums, divisor, threshold)Helper function to check if divisor is valid

if (total > threshold)Early return to avoid unnecessary work

if (isFeasible(nums, mid, threshold))Binary search decision based on helper

let low = 1, high = Math.max(...nums);Initialize binary search bounds

⏱

Complexity

TimeO(n log(max(nums)))

SpaceO(1)

Same as previous approach but with clearer code structure and early exits in feasibility check.

💡 This approach is easier to maintain and debug, which is valuable in interviews.

Interview Verdict: Accepted

This is the recommended approach for interviews due to clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Binary search with helper is the best balance of clarity and efficiency and should be coded in most interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * max(nums))	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search on Divisor	O(n log(max(nums)))	O(1)	No	N/A	Code this for efficient solution
3. Binary Search with Helper Function	O(n log(max(nums)))	O(1)	No	N/A	Preferred approach for clarity and maintainability

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to communicate your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce binary search on the answer space and why it works.Step 4: Implement the binary search with a helper feasibility function for clarity.Step 5: Test your code with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, implement ceiling division correctly, and optimize brute force to efficient solution.

Common Follow-ups

• What if threshold is smaller than array length? → No valid divisor, handle edge case.
• Can you optimize space or runtime further? → Early exit in feasibility check.

💡 These follow-ups test your edge case handling and code optimization skills.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum or maximum value satisfying a condition; 2) Condition can be checked efficiently; 3) Condition is monotonic with respect to the answer; 4) Direct search is too slow.

Signature Phrases

smallest divisorsum of ceil divisionsthreshold limit

NOT This Pattern When

Standard binary search on sorted arrays or searching for elements, which is different from searching answer space.

Similar Problems

Split Array Largest Sum - binary search on max subarray sumCapacity To Ship Packages Within D Days - binary search on ship capacity

Practice

1. You are given a sorted array and need to efficiently find the index of a target value or determine it is not present. Which algorithmic approach guarantees the fastest search in O(log n) time by repeatedly dividing the search interval in half?

easy

A. Linear search by scanning each element until the target is found

B. Greedy algorithm selecting the closest element at each step

C. Binary search by repeatedly halving the search range based on comparisons

D. Dynamic programming to build a table of subproblems for target lookup

Solution

1. Step 1: Understand problem constraints

   The array is sorted, enabling divide-and-conquer strategies.

2. Step 2: Identify algorithm matching O(log n) search

   Binary search halves the search space each step, guaranteeing O(log n) time, unlike linear or greedy approaches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search is the classic O(log n) search on sorted arrays [OK]

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

Common Mistakes:

• Confusing greedy or DP with binary search
• Assuming linear scan is optimal
• Thinking DP applies to simple search

2. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a greedy approach by repeatedly picking the smallest element from the matrix without extra data structures.

B. Flatten the matrix into a list, sort it, and return the kth element.

C. Apply dynamic programming to build a table of smallest elements up to k.

D. Use a min-heap to merge the sorted rows, extracting the smallest elements until the kth is found.

Solution

1. Step 1: Understand problem constraints

   The matrix rows and columns are sorted, so each row is sorted and each column is sorted independently.

2. Step 2: Identify the optimal approach

   Using a min-heap to merge sorted rows efficiently extracts the smallest elements in ascending order, achieving O(k log n) time, better than flattening and sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges sorted lists optimally [OK]

Hint: Min-heap merges sorted rows efficiently [OK]

Common Mistakes:

• Assuming flatten and sort is optimal
• Confusing DP with this problem
• Thinking greedy without data structures works

3. The following code attempts to compute the integer square root using Newton's method. Which line contains a subtle bug that can cause incorrect results or infinite loops for inputs 0 or 1?

medium

A. Line 1: def mySqrt(x: int) -> int:

B. Line 2: guess = x // 2

C. Line 3: while guess * guess > x:

D. Line 4: guess = (guess + x // guess) // 2

Solution

1. Step 1: Identify missing base case handling

   The code does not handle x=0 or x=1 explicitly, which can cause guess to be 0 and lead to division by zero or infinite loop.

2. Step 2: Pinpoint the bug line

   Line 2 initializes guess = x // 2 without checking if x < 2, causing issues for small inputs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Proper base case handling prevents infinite loops [OK]

Hint: Always handle small inputs before iterative methods [OK]

Common Mistakes:

• Ignoring base cases
• Assuming guess initialization always valid
• Misplacing loop condition

4. Suppose now you want to make bouquets but flowers can be reused multiple times (i.e., each flower can be counted multiple times for different bouquets). Which modification to the algorithm is correct?

hard

A. Keep the same binary search and feasibility check, but remove resetting flowers count to zero on encountering a flower that blooms after the day.

B. Binary search is no longer applicable; instead, use a greedy approach to pick flowers repeatedly until bouquets are formed.

C. Use binary search on days, but feasibility must count bouquets by grouping any flowers bloomed by day, allowing reuse by not resetting flowers count.

D. Modify feasibility to count total flowers bloomed by day and check if total flowers >= m * k, ignoring adjacency.

Solution

1. Step 1: Understand reuse changes adjacency constraint

   If flowers can be reused multiple times, adjacency no longer matters; only total count of bloomed flowers by day matters.

2. Step 2: Modify feasibility check

   Feasibility reduces to checking if total bloomed flowers by day >= m * k, ignoring adjacency and resetting.

3. Step 3: Binary search remains valid

   Binary search on days still applies, but feasibility is simplified to total count check.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting total bloomed flowers matches reuse scenario. [OK]

Hint: Reuse removes adjacency; feasibility counts total bloomed flowers [OK]

Common Mistakes:

• Ignoring adjacency but still resetting flowers count
• Removing binary search unnecessarily

5. Suppose the rotated sorted array may contain duplicate elements. Which modification to the pivot-finding algorithm is necessary to correctly find the pivot in O(log n) time in the worst case?

hard

A. Add a linear scan fallback when nums[mid] == nums[high] to reduce high by one.

B. Use a hash map to store visited indices to avoid infinite loops.

C. No modification needed; the existing pivot-finding algorithm works unchanged.

D. Switch to linear search for pivot since duplicates break binary search.

Solution

1. Step 1: Understand duplicates impact

   Duplicates can cause nums[mid] == nums[high], making it unclear which half is sorted.

2. Step 2: Modify pivot search

   When nums[mid] == nums[high], reduce high by one to shrink search space safely.

3. Step 3: Complexity consideration

   This modification keeps worst-case complexity close to O(n) but often better than linear scan.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reducing high on equality handles duplicates correctly [OK]

Hint: Handle nums[mid]==nums[high] by decrementing high [OK]

Common Mistakes:

• Assuming no duplicates
• Switching to linear search unnecessarily