Find the Smallest Divisor Given a Threshold

Find the Smallest Divisor Given a Threshold - Problem

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array elements by it, and sum the division's result.

Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of the division is rounded to the nearest integer greater than or equal to that element (ceiling function). For example: 7/3 = 3 and 10/2 = 5.

The test cases are generated so that there will be an answer.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: With divisor 5: ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5 ≤ 6. Smaller divisors give larger sums, so 5 is the answer.

Example 2 — Larger Threshold

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

› Output: 44

💡 Note: With divisor 44: ceil(44/44) + ceil(22/44) + ceil(33/44) + ceil(11/44) + ceil(1/44) = 1 + 1 + 1 + 1 + 1 = 5 ≤ 5

Example 3 — Small Array

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

› Output: 3

💡 Note: With divisor 3: ceil(2/3) + ceil(3/3) + ceil(5/3) + ceil(7/3) + ceil(11/3) = 1 + 1 + 2 + 3 + 4 = 11 ≤ 11

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 10⁶
nums.length ≤ threshold ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,5,9] with threshold 6

Process

Test divisors and calculate ceiling division sums

Output

Smallest divisor where sum ≤ threshold

Key Takeaway

🎯 Key Insight: As divisor increases, the sum decreases monotonically, making binary search the perfect optimization

Asked in

a Amazon 15 f Facebook 12 G Google 8

The key insight is that as the divisor increases, the sum of ceiling divisions decreases monotonically. This allows us to use binary search on the answer space from 1 to max(nums). For each candidate divisor, we calculate the sum of ceil(nums[i]/divisor) and check if it's ≤ threshold. Best approach is binary search with Time: O(n × log(max(nums))), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(n × log(max(nums)))	O(1)	Use binary search to efficiently find the smallest valid divisor
Brute Force Linear Search	O(n × max(nums))	O(1)	Try every divisor from 1 upward until finding one that gives sum ≤ threshold

Binary Search on Answer Space — Algorithm Steps

Set left = 1, right = max(nums)
For each mid divisor, calculate sum of ceiling divisions
If sum ≤ threshold, try smaller divisors (right = mid)
If sum > threshold, try larger divisors (left = mid + 1)
Return the smallest valid divisor

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize range

Set left=1, right=max(nums)

Test middle

Calculate sum for mid divisor

Narrow range

Move left or right based on sum vs threshold

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int solution(int* nums, int numsSize, int threshold) {
    int left = 1;
    int right = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > right) {
            right = nums[i];
        }
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        long long total = 0;
        
        for (int i = 0; i < numsSize; i++) {
            total += (long long)ceil((double)nums[i] / mid);
        }
        
        if (total <= threshold) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int threshold;
    scanf("%d", &threshold);
    
    int result = solution(nums, numsSize, threshold);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max(nums)))

Binary search runs log(max(nums)) iterations, each calculating sum over n elements

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search bounds

✓ Linear Space

87.4K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler