Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find the Smallest Divisor Given a Threshold

MEDIUMProblemSolveExternal Links

Description

Given an array of integers nums and an integer threshold, choose a positive integer divisor, divide every element in the array by it, round each result up to the nearest integer (ceiling division), and sum all the rounded results.

Find the smallest divisor such that the sum described above is less than or equal to threshold.

For example, dividing 7 by 3 gives ⌈7/3⌉ = 3, and dividing 10 by 2 gives ⌈10/2⌉ = 5.

The problem guarantees that a valid answer always exists.

Examples

Example 1

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

Output: 5

Explanation:

  • Divisor = 1: ⌈1/1⌉ + ⌈2/1⌉ + ⌈5/1⌉ + ⌈9/1⌉ = 1 + 2 + 5 + 9 = 17 > 6. ✗
  • Divisor = 4: ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 7 > 6. ✗
  • Divisor = 5: ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 5 ≤ 6. ✓

5 is the smallest divisor that brings the sum to at most 6.

Example 2

Input: nums = [44, 22, 33, 11, 1], threshold = 5

Output: 44

Explanation:

  • Divisor = 44: ⌈44/44⌉ + ⌈22/44⌉ + ⌈33/44⌉ + ⌈11/44⌉ + ⌈1/44⌉ = 1 + 1 + 1 + 1 + 1 = 5 ≤ 5. ✓
  • Divisor = 43: ⌈44/43⌉ + ⌈22/43⌉ + ⌈33/43⌉ + ⌈11/43⌉ + ⌈1/43⌉ = 2 + 1 + 1 + 1 + 1 = 6 > 5. ✗

The smallest valid divisor is 44. Any divisor less than 44 makes the sum exceed the threshold.

Example 3

Input: nums = [2, 3, 5, 7, 11], threshold = 11

Output: 3

Explanation:

  • Divisor = 3: ⌈2/3⌉ + ⌈3/3⌉ + ⌈5/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 1 + 2 + 3 + 4 = 11 ≤ 11. ✓
  • Divisor = 2: ⌈2/2⌉ + ⌈3/2⌉ + ⌈5/2⌉ + ⌈7/2⌉ + ⌈11/2⌉ = 1 + 2 + 3 + 4 + 6 = 16 > 11. ✗

Divisor 3 is the smallest value where the ceiling-division sum does not exceed 11.

Constraints

  • 1 ≤ nums.length ≤ 5 × 10^4
  • 1 ≤ nums[i] ≤ 10^6
  • nums.length ≤ threshold ≤ 10^6

Editorial

Brute Force

Intuition

The most natural way to solve this problem is to try every possible divisor starting from 1 and going upward. For each divisor, compute the sum of ceiling divisions across all elements. The first divisor where this sum falls at or below the threshold is our answer.

Think of it like adjusting a dial on a machine. You start at the lowest setting (divisor = 1) and slowly turn it up. At each setting, you measure the total output (ceiling-division sum). The moment the output drops to an acceptable level (≤ threshold), you stop — that is the smallest valid divisor.

Why start from 1? Because we want the smallest divisor, and divisor = 1 gives the largest possible sum (no reduction). As the divisor grows, each ceiling-division result can only stay the same or decrease, so the sum is monotonically non-increasing. The first time it drops at or below the threshold, we have our answer.

The ceiling division ⌈a/d⌉ can be computed without floating-point math using the integer formula: (a + d - 1) / d or equivalently (a - 1) / d + 1.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 5, 9], threshold = 6.

The maximum element is 9, so the divisor ranges from 1 to 9 (any divisor > max(nums) gives the same sum as max(nums) since all ceil divisions become 1).

Step 1: divisor = 1.

  • ⌈1/1⌉ + ⌈2/1⌉ + ⌈5/1⌉ + ⌈9/1⌉ = 1 + 2 + 5 + 9 = 17.
  • 17 > 6 → too large. Try next divisor.

Step 2: divisor = 2.

  • ⌈1/2⌉ + ⌈2/2⌉ + ⌈5/2⌉ + ⌈9/2⌉ = 1 + 1 + 3 + 5 = 10.
  • 10 > 6 → still too large.

Step 3: divisor = 3.

  • ⌈1/3⌉ + ⌈2/3⌉ + ⌈5/3⌉ + ⌈9/3⌉ = 1 + 1 + 2 + 3 = 7.
  • 7 > 6 → still too large.

Step 4: divisor = 4.

  • ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 7.
  • 7 > 6 → still too large.

Step 5: divisor = 5.

  • ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 5.
  • 5 ≤ 6 → SUCCESS! This is the smallest valid divisor.

Result: Return 5.

Brute Force — Trying Every Divisor — Watch how we compute the ceiling-division sum for each divisor from 1 upward, stopping at the first divisor where the sum meets the threshold.

Algorithm

  1. Find maxVal = max(nums).
  2. For each divisor d from 1 to maxVal:
    a. Compute sum = Σ ⌈nums[i] / d⌉ for all elements.
    b. If sum ≤ threshold, return d.
  3. Return maxVal (guaranteed to work since threshold ≥ nums.length).

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int maxVal = *max_element(nums.begin(), nums.end());
        
        for (int d = 1; d <= maxVal; d++) {
            int sum = 0;
            for (int num : nums) {
                sum += (num + d - 1) / d;  // ceiling division
            }
            if (sum <= threshold) return d;
        }
        
        return maxVal;
    }
};
import math

class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        max_val = max(nums)
        
        for d in range(1, max_val + 1):
            total = sum(math.ceil(num / d) for num in nums)
            if total <= threshold:
                return d
        
        return max_val
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int maxVal = 0;
        for (int num : nums) maxVal = Math.max(maxVal, num);
        
        for (int d = 1; d <= maxVal; d++) {
            int sum = 0;
            for (int num : nums) {
                sum += (num + d - 1) / d;  // ceiling division
            }
            if (sum <= threshold) return d;
        }
        
        return maxVal;
    }
}

Complexity Analysis

Time Complexity: O(max(nums) × n)

We try up to max(nums) divisors (up to 10^6), and for each divisor we iterate through all n elements (up to 5 × 10^4) to compute the ceiling-division sum. In the worst case, this is 10^6 × 5 × 10^4 = 5 × 10^10 operations — far too slow.

Space Complexity: O(1)

We only use a few integer variables (d, sum, maxVal). No additional data structures needed.

Why This Approach Is Not Efficient

The brute force iterates through every possible divisor from 1 to max(nums). With max(nums) up to 10^6 and array length up to 5 × 10^4, each iteration scans the entire array. This yields up to 5 × 10^10 operations, which is orders of magnitude beyond the typical time limit of ~10^8 operations per second.

The crucial observation is that the ceiling-division sum is a monotonically non-increasing function of the divisor:

  • Divisor = 1 gives the maximum possible sum (the raw sum of elements).
  • As the divisor grows, each ⌈nums[i]/d⌉ can only decrease or stay the same.
  • Divisor = max(nums) gives the minimum possible sum (each element contributes exactly 1).

Because the sum is monotonically non-increasing, there is a clear transition point: all divisors below the answer give sums that exceed the threshold, and all divisors at or above the answer give sums within the threshold. This is the classic signature of a binary search problem — we can find this transition point in O(log(max(nums))) probes instead of O(max(nums)) linear scans.

Optimal Approach - Binary Search on Answer

Intuition

Since the ceiling-division sum decreases monotonically as the divisor increases, we can binary search for the smallest divisor that keeps the sum within the threshold.

Imagine lining up all possible divisors from 1 to max(nums) on a number line. The sums they produce look like a staircase descending from left to right. Somewhere on this staircase, the sum drops from above the threshold to at or below it. We want to find that exact step.

Rather than walking the staircase one step at a time (brute force), we jump to the middle, check which side of the threshold we are on, and eliminate half the remaining candidates. This is binary search.

The search space is [1, max(nums)]:

  • low = 1 (smallest possible divisor).
  • high = max(nums) (beyond this, every element's ceiling is 1, giving sum = n, which is guaranteed ≤ threshold since threshold ≥ n).

At each step, compute mid = (low + high) / 2 and check the ceiling-division sum:

  • If the sum ≤ threshold, then mid is a valid divisor, but there might be a smaller one. Set high = mid.
  • If the sum > threshold, then mid is too small. Set low = mid + 1.

When low == high, we have found the smallest valid divisor.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 5, 9], threshold = 6.

Search range: low = 1, high = max(nums) = 9.

Step 1: mid = (1 + 9) / 2 = 5.

  • Compute sum: ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 5.
  • 5 ≤ 6 → valid. There might be a smaller divisor. Set high = 5.

Step 2: mid = (1 + 5) / 2 = 3.

  • Compute sum: ⌈1/3⌉ + ⌈2/3⌉ + ⌈5/3⌉ + ⌈9/3⌉ = 1 + 1 + 2 + 3 = 7.
  • 7 > 6 → invalid. Divisor 3 is too small. Set low = 4.

Step 3: mid = (4 + 5) / 2 = 4.

  • Compute sum: ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 7.
  • 7 > 6 → invalid. Set low = 5.

Step 4: low = 5, high = 5. low == high → converged.

Result: The smallest divisor is 5.

Binary Search on Divisor — Finding the Threshold Boundary — Watch how binary search narrows the divisor range. For each candidate divisor, we compute the ceiling-division sum and decide which half to keep.

Algorithm

  1. Set low = 1, high = max(nums).
  2. While low < high:
    a. Compute mid = low + (high - low) / 2.
    b. Compute sum = Σ ⌈nums[i] / mid⌉ for all elements.
    c. If sum ≤ threshold, set high = mid (this divisor works, but a smaller one might too).
    d. Otherwise, set low = mid + 1 (this divisor is too small).
  3. Return low.

Computing ceiling division without floating point:

  • ⌈a / d⌉ = (a + d - 1) / d (integer division)

Code

#include <vector>
#include <algorithm>
using namespace std;

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

class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        low = 1
        high = max(nums)
        
        while low < high:
            mid = low + (high - low) // 2
            total = sum(math.ceil(num / mid) for num in nums)
            if total <= threshold:
                high = mid
            else:
                low = mid + 1
        
        return low
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int low = 1;
        int high = 0;
        for (int num : nums) high = Math.max(high, num);
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            int sum = 0;
            for (int num : nums) {
                sum += (num + mid - 1) / mid;
            }
            if (sum <= threshold) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        return low;
    }
}

Complexity Analysis

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

The binary search operates over the range [1, max(nums)]. With max(nums) up to 10^6, binary search performs at most log₂(10^6) ≈ 20 iterations. Each iteration scans the entire array of n elements to compute the ceiling-division sum. Total: O(n × 20) = O(n × log(max(nums))).

For n = 5 × 10^4, this is about 10^6 operations — extremely fast.

Space Complexity: O(1)

We only use a constant number of variables (low, high, mid, sum). No extra data structures are needed beyond the input array.