BS-14. Find the Smallest Divisor Given a Threshold | Binary Search

This chapter explores how to find the optimal positive integer divisor such that the sum of the ceiling values of array elements divided by that divisor is less than or equal to a given threshold. We will progress from a naive linear search to an optimal Binary Search on Answers solution.

1. Problem Statement & Core Objective

Given an array of integers and an integer threshold value, our task is to find the smallest divisor such that when every element in the array is divided by this divisor, and the individual ceiling values of each division are summed up, the total sum is less than or equal to the threshold.

Mathematical Formulation

For an array $A = [a_0, a_1, \dots, a_{n-1}]$ and a divisor $d$, we calculate:

We need to find the minimum $d \ge 1$ such that:

2. Real-Life Mental Model & Analogy

Real-Life Analogy: The Portion Cutter

Imagine you have a pile of heavy stone blocks of varying weights (represented by the array elements). You want to pack these blocks into smaller shipping containers of capacity $d$. Because fractional containers aren't allowed, any leftover fraction of a block requires an entirely new container (hence the ceiling function).

• If your container size $d$ is very small (e.g., $1$), every block gets its own container (or multiple containers), leading to a huge total count that exceeds your shipping limit (threshold).
• If your container size $d$ is very large, everything fits into fewer containers than your limit.
• Your goal is to find the smallest container size that keeps the total number of containers under or equal to your threshold limit.

3. Working Example Walkthrough

Consider:

• Array $A = [1, 2, 5, 9]$
• Threshold $= 7$

Let's test different divisors ($d$):

Among all valid divisors ($3, 4, 5, \dots$), the smallest divisor is $3$ (or $5$ depending on array values and threshold constraints; let's verify with the transcript's specific threshold walkthrough where threshold $= 7$, divisor $3$ gives sum $7$, which is $\le 7$).

4. Naive Linear Search Approach

Status Quo & Logic

• We know the divisor cannot be $0$ or negative. Positive divisors start from $1$.
• What is the maximum possible divisor we ever need to check? The maximum element in the array (Max). Dividing any element by a number larger than itself results in $0.something$, whose ceiling is 1. Thus, pushing the divisor beyond the maximum array element yields the minimum possible sum (which equals the size of the array, $N$).
• Therefore, our search space for the divisor is strictly bounded between 1 and Max(Array).

Naive Implementation Code

int smallestDivisor(vector<int>& nums, int threshold) {
    int maxElement = *max_element(nums.begin(), nums.end());
    
    for (int d = 1; d <= maxElement; d++) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += ceil((double)(nums[i]) / d);
        }
        if (sum <= threshold) {
            return d; // First valid divisor found is the smallest
        }
    }
    return -1;
}

Complexity Analysis

• Time Complexity: $O(\text{Max} \times N)$, where $\text{Max}$ is the maximum element in the array and $N$ is the number of elements. If $\text{Max}$ is large (e.g., $10^6$), this approach will result in a Time Limit Exceeded (TLE) error.
• Space Complexity: $O(1)$ auxiliary space.

5. Transitioning to Binary Search on Answers

Why Binary Search Applies

1. Monotonic Range: We are looking for a minimum value within a known range $[1, \text{Max}(A)]$.
2. Monotonic Behavior:
   • If a divisor $d$ is too small, the division sums will be too large, violating the threshold.
   • If we increase the divisor, the sum strictly decreases or remains constant (monotonic property).
   • Once a divisor is valid, all larger divisors are also valid. Once a divisor is invalid, all smaller divisors are also invalid.

Divisor:   1    2    3    4    5    6    7    8    9 (Max)
Validity:  No   No   Yes  Yes  Yes  Yes  Yes  Yes  Yes
             (Invalid Zone)       |     (Valid Zone)
                                  v
                             Smallest Valid (Our Target)

6. Step-by-Step Binary Search Execution Flow

1. Initialize Pointers:

   • low = 1
   • high = Max(Array)
   • ans = -1

2. Compute Mid:

   • mid = low + (high - low) / 2

3. Evaluate Sum at mid:

   • Helper function computes $\sum \lceil A[i] / \text{mid} \rceil$.

4. Adjust Search Space:

   • If $\text{Sum} \le \text{Threshold}$: This mid is a valid candidate. Store ans = mid, and since we want the smallest divisor, eliminate the right half (high = mid - 1).
   • If $\text{Sum} > \text{Threshold}$: This mid is invalid. We need a larger divisor, so eliminate the left half (low = mid + 1).

7. Complete Optimized Code Implementation

Here is the robust, production-grade implementation in C++:

#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
private:
    // Helper function to calculate total sum of divisions for a given divisor (d)
    int calculateSum(const std::vector<int>& nums, int d) {
        int sum = 0;
        for (int num : nums) {
            sum += std::ceil((double)(num) / (double)(d));
        }
        return sum;
    }

public:
    int smallestDivisor(std::vector<int>& nums, int threshold) {
        int low = 1;
        int high = *std::max_element(nums.begin(), nums.end());
        int smallestValidDivisor = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (calculateSum(nums, mid) <= threshold) {
                smallestValidDivisor = mid; // Record valid answer
                high = mid - 1;            // Try to find a smaller divisor on the left
            } else {
                low = mid + 1;             // Sum too large, need a larger divisor on the right
            }
        }

        return smallestValidDivisor;
    }
};

8. Industry Reality, Edge Cases & Debugging

1. Integer Division Pitfall

• The Issue: In languages like C++, Java, or Python, dividing two integers (a / b) performs integer truncation (rounding down), not ceiling division.
• The Fix: Cast operands to double or float before passing them to ceil(), or use integer arithmetic tricks to simulate ceiling without floating-point inaccuracies:

// Integer division ceiling equivalent:
sum += (num + d - 1) / d;

2. Impossible Threshold Scenarios (Edge Case)

• What if even the maximum possible divisor (Max(Array)) cannot bring the sum under the threshold?
• Proof: The minimum possible sum you can achieve is when dividing every element by the maximum element of the array, which yields $1$ for each element, resulting in a total sum equal to the array size $N$ (nums.size()).
• If Threshold < nums.size(), it is mathematically impossible to satisfy the condition, and the function should return -1.

9. Complexity Analysis of Binary Search Solution

• Time Complexity: $O(N \log(\text{Max}))$, where $N$ is the size of the array and $\text{Max}$ is the maximum element in nums. The binary search runs in $\log(\text{Max})$ iterations, and inside each iteration, we traverse the array of size $N$ to calculate the division sum.
• Space Complexity: $O(1)$ auxiliary space, as no extra data structures are used.

10. Summary and Key Takeaways

• Problem Type: Finding the minimum value within a monotonic range perfectly maps to Binary Search on Answers.
• Search Space Bounds: The divisor search range always lies between 1 and the maximum element in the array (Max).
• Ceiling Division: Always account for fractional remainders by using ceiling operations (ceil()) or integer ceiling arithmetic (num + d - 1) / d.
• Optimization Impact: Upgraded time complexity from linear $O(\text{Max} \times N)$ to logarithmic $O(N \log(\text{Max}))$.
• Pointer Behavior: When searching for the minimum valid answer, store the valid mid and shrink the search space to the left (high = mid - 1).