Find the Smallest Divisor Given a Threshold

Problem statement

You get a positive integer array nums and an integer threshold. Pick a positive divisor d and replace every nums[i] with ceil(nums[i] / d), then sum those values. Return the smallest d such that this sum is at most threshold.

Example:

Input:

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

Expected output:

5

Why: with d = 5, the ceiled quotients sum to 1 + 1 + 1 + 2 = 5 ≤ 6, and no smaller valid d works as well for this input family of checks.

Practice on LeetCode: Find the Smallest Divisor Given a Threshold

Golang Solution

Binary-search d between 1 and max(nums). For a candidate mid, compute the ceiled sum; if it fits under threshold, try a smaller divisor, otherwise go higher.

Time: O(n log M) — M is the largest value in nums
Space: O(1)

import "math"

func smallestDivisor(nums []int, threshold int) int {
    low, high := 1, 0

    for _, num := range nums {
        if num > high {
            high = num
        }
    }

    for low <= high {
        mid := low + (high-low)/2

        temp := 0
        for i := 0; i < len(nums); i++ {
            temp += int(math.Ceil(float64(nums[i]) / float64(mid)))
        }

        if temp <= threshold {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return low
}