Find the Smallest Divisor Given a Threshold

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.

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.

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.

#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;
}

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

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 = *max_element(nums, nums + n), ans = high;
    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]);
    cout << "Smallest Divisor: " << smallestDivisor(nums, n, threshold) << endl;
    return 0;
}

import math

def smallestDivisor(nums, threshold):
    def compute_sum(divisor):
        return sum(math.ceil(num / divisor) for num in nums)

    low, high = 1, max(nums)
    answer = high
    while low <= high:
        mid = (low + high) // 2
        if compute_sum(mid) <= threshold:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

nums = [1, 2, 5, 9]
threshold = 6
print("Smallest Divisor:", smallestDivisor(nums, threshold))

public class Main {
    public static int smallestDivisor(int[] nums, int threshold) {
        int low = 1, high = Integer.MIN_VALUE;
        for (int num : nums) {
            high = Math.max(high, num);
        }
        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int sum = 0;
            for (int num : nums) {
                sum += (num + mid - 1) / mid;
            }
            if (sum <= threshold) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

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

function smallestDivisor(nums, threshold) {
    const computeSum = (divisor) =>
        nums.reduce((sum, num) => sum + Math.ceil(num / divisor), 0);

    let low = 1, high = Math.max(...nums), answer = high;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (computeSum(mid) <= threshold) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

const nums = [1, 2, 5, 9];
const threshold = 6;
console.log("Smallest Divisor:", smallestDivisor(nums, threshold));

package main

import (
    "fmt"
    "math"
)

func computeSum(nums []int, divisor int) int {
    sum := 0
    for _, num := range nums {
        sum += int(math.Ceil(float64(num) / float64(divisor)))
    }
    return sum
}

func smallestDivisor(nums []int, threshold int) int {
    low, high := 1, nums[0]
    for _, num := range nums {
        if num > high {
            high = num
        }
    }
    ans := high
    for low <= high {
        mid := (low + high) / 2
        if computeSum(nums, mid) <= threshold {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

func main() {
    nums := []int{1, 2, 5, 9}
    threshold := 6
    fmt.Println("Smallest Divisor:", smallestDivisor(nums, threshold))
}

fn compute_sum(nums: &Vec<i32>, divisor: i32) -> i32 {
    nums.iter().map(|&x| (x + divisor - 1) / divisor).sum()
}

fn smallest_divisor(nums: Vec<i32>, threshold: i32) -> i32 {
    let mut low = 1;
    let mut high = *nums.iter().max().unwrap();
    let mut ans = high;
    while low <= high {
        let mid = (low + high) / 2;
        let sum = compute_sum(&nums, mid);
        if sum <= threshold {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    ans
}

fn main() {
    let nums = vec![1, 2, 5, 9];
    let threshold = 6;
    println!("Smallest Divisor: {}", smallest_divisor(nums, threshold));
}

fun computeSum(nums: IntArray, divisor: Int): Int {
    return nums.sumOf { (it + divisor - 1) / divisor }
}

fun smallestDivisor(nums: IntArray, threshold: Int): Int {
    var low = 1
    var high = nums.maxOrNull() ?: 1
    var ans = high
    while (low <= high) {
        val mid = (low + high) / 2
        val sum = computeSum(nums, mid)
        if (sum <= threshold) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

fun main() {
    val nums = intArrayOf(1, 2, 5, 9)
    val threshold = 6
    println("Smallest Divisor: ${smallestDivisor(nums, threshold)}")
}

import Foundation

func computeSum(_ nums: [Int], _ divisor: Int) -> Int {
    return nums.reduce(0) { $0 + Int(ceil(Double($1) / Double(divisor))) }
}

func smallestDivisor(_ nums: [Int], _ threshold: Int) -> Int {
    var low = 1
    var high = nums.max() ?? 1
    var answer = high
    while low <= high {
        let mid = (low + high) / 2
        if computeSum(nums, mid) <= threshold {
            answer = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return answer
}

let nums = [1, 2, 5, 9]
let threshold = 6
print("Smallest Divisor: \(smallestDivisor(nums, threshold))")

function smallestDivisor(nums: number[], threshold: number): number {
    const computeSum = (divisor: number): number =>
        nums.reduce((sum, num) => sum + Math.ceil(num / divisor), 0);

    let low = 1, high = Math.max(...nums), answer = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (computeSum(mid) <= threshold) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

const nums: number[] = [1, 2, 5, 9];
const threshold: number = 6;
console.log("Smallest Divisor:", smallestDivisor(nums, threshold));

Time complexity

Space complexity

O(1)

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