We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Smallest Divisor Given a Threshold

Number: 1408

Difficulty: Medium

Paid? No

Companies: Google, Amazon, DE Shaw, Meta, ZScaler, Agoda, PayPal, Expedia, Apple, Oracle

Problem Description

Given an array of positive integers and a threshold, determine the smallest positive divisor such that the sum of the ceiling of each number divided by the divisor is less than or equal to the threshold.

Key Insights

  • The division results are rounded up (ceiling function).
  • Increasing the divisor decreases each term of the sum because the quotient decreases.
  • The problem hints at a binary search solution over the possible divisor values.
  • The minimum divisor is 1 and the maximum divisor can be set as the maximum value in the array.

Space and Time Complexity

Time Complexity: O(N * log(max_num)) where N is the length of the array and max_num is the maximum element in the array. Space Complexity: O(1), since only constant extra space is used.

Solution

We perform a binary search over the range [1, max(nums)]. For each candidate divisor:

  1. Calculate the sum by taking the ceiling of the division (i.e., (num + divisor - 1) // divisor for each number).
  2. If the sum is <= threshold, then the candidate might be valid and we try to find a smaller divisor in the left half.
  3. Otherwise, if sum > threshold, we need a larger divisor, so we search the right half. This binary search efficiently reduces the search space by leveraging the monotonic behavior of the sum with respect to the divisor.

Code Solutions

# Python solution with line-by-line comments

def smallestDivisor(nums, threshold):
    # Helper function to compute the sum with a given divisor
    def compute_sum(divisor):
        total = 0
        for num in nums:
            # Using the formula (num + divisor - 1) // divisor to get ceiling division
            total += (num + divisor - 1) // divisor  
        return total

    low, high = 1, max(nums)  # initialize the search range
    
    while low < high:
        mid = (low + high) // 2  # candidate divisor
        if compute_sum(mid) > threshold:
            # If the computed sum is greater than threshold, increase the divisor
            low = mid + 1
        else:
            # Otherwise, try to see if a smaller divisor can still satisfy the condition
            high = mid
    return low

# Example usage:
print(smallestDivisor([1, 2, 5, 9], 6))
← Back to All Questions