Smallest Divisor Greater Than Threshold Optimal Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a list of positive integers nums and a positive integer threshold. Your task is to find the smallest positive integer divisor such that the sum of all elements in the array when each is divided by this divisor (rounded up) is less than or equal to threshold.

  • For each number in the array, you must compute ceil(num / divisor).
  • The final sum of these values must not exceed the given threshold.

If nums is empty or threshold is not a valid positive number, return -1.

Examples❯

Input Array Threshold Smallest Divisor Description
[1, 2, 5, 9] 6 5 Dividing with 5: ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5) = 1+1+1+2 = 5 ≤ 6
[2, 3, 5, 7, 11] 11 3 Dividing with 3 gives total sum 9, which is ≤ threshold
[19] 5 4 We need to divide 19 so that ceil(19/divisor) ≤ 5
[1, 2, 3] 3 1 Any number divided by 1 will result in original value, sum = 6, so must search for larger divisor
[100, 200, 300] 3 300 Only a very large divisor can reduce the sum below threshold
[1] 1 1 Only one number, and we need sum ≤ 1, so divisor = 1
[] 5 -1 Empty array, nothing to divide
[1, 2, 3] 0 -1 Threshold is invalid (non-positive)

Solution❯

Understanding the Problem

We are given an array of positive integers and a threshold. Our goal is to find the smallest positive divisor such that when each number in the array is divided by this divisor and rounded up (using the ceiling function), the total sum of these results is less than or equal to the threshold.

Let’s look at an example to make it clear. Suppose:

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

If we try divisor = 5, the results of ceiling division are:

  • ceil(1 / 5) = 1
  • ceil(2 / 5) = 1
  • ceil(5 / 5) = 1
  • ceil(9 / 5) = 2

The total sum is 1 + 1 + 1 + 2 = 5, which is less than or equal to the threshold 6. Hence, 5 is a valid divisor. But is it the smallest one? That’s what we need to figure out.

Step-by-Step Solution with Example

Step 1: Understand ceiling division

For any number x and divisor d, ceil(x/d) means rounding the result up. For example, ceil(9/4) = 3, not 2. This helps ensure that the result is always at least as large as the exact division, rounded up.

Step 2: Define the problem as a search problem

We can treat the search for the smallest divisor as a range of numbers from 1 to the max(nums). For each value in this range, we calculate the total of all ceil(num / divisor) and check if it’s less than or equal to the threshold.

Step 3: Use binary search to optimize

Trying each number one-by-one would be slow. Instead, we use binary search:

  • Start with low = 1 and high = max(nums)
  • At each step, pick mid = (low + high) / 2 and calculate the total sum using this mid as the divisor
  • If the sum is within the threshold, try smaller divisors (high = mid - 1)
  • Otherwise, try larger divisors (low = mid + 1)

Step 4: Walk through the example

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

  • Start with low = 1, high = 9
  • mid = 5 ➝ total = 5 (valid) ➝ try smaller (high = 4)
  • mid = 2 ➝ total = ceil(1/2)+ceil(2/2)+ceil(5/2)+ceil(9/2) = 1+1+3+5 = 10 ➝ too big ➝ try larger (low = 3)
  • mid = 3 ➝ total = 1+1+2+3 = 7 ➝ too big ➝ try larger (low = 4)
  • mid = 4 ➝ total = 1+1+2+3 = 7 ➝ too big ➝ try larger (low = 5)

At the end, we settle on divisor = 5 as the smallest valid divisor.

Edge Cases

  • Empty array: There are no elements to divide. Return -1.
  • Threshold is 0 or negative: It’s impossible to satisfy the requirement. Return -1.
  • All numbers are 1: Any divisor ≥ 1 results in a sum equal to the length of the array.
  • Very large numbers: Binary search ensures that we only do log(max) checks, so it stays efficient.

Finally

This problem is a great example of turning a mathematical challenge into an efficient algorithm. By using binary search over possible divisors, we quickly narrow down to the smallest one that meets the threshold. This approach handles large inputs well and avoids brute-force inefficiencies.

Always remember to consider edge cases and validate inputs before applying the main logic. And when you see a problem asking for “minimum x that satisfies a condition,” binary search is often your best friend.

Algorithm Steps❯

  1. Initialize low = 1 and high = max(nums).
  2. While low ≤ high:
  3. → Calculate mid as the potential divisor.
  4. → Compute sum = sum(ceil(num / mid) for num in nums).
  5. → If sum ≤ threshold: store mid as potential answer, and search for smaller divisor by setting high = mid - 1.
  6. → Else: search higher by setting low = mid + 1.
  7. Return the smallest valid divisor found.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <math.h>

int computeSum(int nums[], int n, int divisor) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += (nums[i] + divisor - 1) / divisor;
    }
    return sum;
}

int smallestDivisor(int nums[], int n, int threshold) {
    int low = 1, high = nums[0], ans = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] > high) high = nums[i];
    }

    while (low <= high) {
        int mid = (low + high) / 2;
        int sum = computeSum(nums, n, mid);

        if (sum <= threshold) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

int main() {
    int nums[] = {1, 2, 5, 9};
    int threshold = 6;
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("Smallest Divisor: %d\n", smallestDivisor(nums, n, threshold));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In each binary search step, computing the sum involves iterating through the entire array.
Average CaseO(n log m)Binary search over range [1, max(nums)], and each step takes O(n) time to compute the sum.
Worst CaseO(n log m)Same as average case — n elements, log(max(nums)) search steps.

Space Complexity❯

O(1)

Explanation: Only a few variables are used; no extra space proportional to input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...