Jobs

Interviews

Discussions

Find the Smallest Divisor Given a Threshold

Medium

Agoda

0 views

Topics:

ArraysBinary Search

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array 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. (For example: 7/3 = 3 and 10/2 = 5).

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

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

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

Constraints:

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 10⁶
nums.length <= threshold <= 10⁶

Try coding it in LeetCode

Find the Smallest Divisor Given a Threshold

Medium

Agoda

0 views

Topics:

ArraysBinary Search

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

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

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

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

Constraints:

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 10⁶
nums.length <= threshold <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the `nums` array and the `threshold` value?
Is it guaranteed that a divisor satisfying the condition will always exist, or should I handle cases where no such divisor is found?
Can the `nums` array be empty?
Is the threshold value guaranteed to be a positive integer?
Could you clarify the rounding behavior? Should I use the ceiling function to round up the results of the divisions?

Brute Force Solution

Approach

We need to find the smallest number that, when used to divide a list of numbers, results in a sum of quotients (rounded up) less than or equal to a given target. The brute force approach involves systematically checking every possible divisor, starting from the smallest, until we find one that works.

Here's how the algorithm would work step-by-step:

Start with the smallest possible divisor, which is 1.
For the current divisor, go through each number in the given list.
Divide each number in the list by the current divisor and round the result up to the nearest whole number.
Add all the rounded-up results together to get a total sum.
Check if the total sum is less than or equal to the given target.
If the total sum is less than or equal to the target, you've found a divisor that works. Since we started with the smallest possible divisor and worked our way up, this must be the smallest divisor that works, so we're done.
If the total sum is greater than the target, increase the divisor by 1 and repeat the process from step 2.

Code Implementation

import math

def find_smallest_divisor(numbers, threshold):
    smallestDivisor = 1

    while True:
        totalSum = 0

        for number in numbers:
            # Round up the division result and add to the total sum
            totalSum += math.ceil(number / smallestDivisor)

        # Check if the total sum satisfies the threshold condition
        if totalSum <= threshold:
            return smallestDivisor

        # Increment the divisor to find the smallest that satisfies condition
        smallestDivisor += 1

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through potential divisors starting from 1. For each divisor (up to 'm', where 'm' is the maximum possible divisor which occurs when the quotient sum first becomes less than or equal to threshold), it iterates through all 'n' numbers in the input array to calculate the sum of rounded-up quotients. Therefore, the number of operations grows linearly with both the size of the input array 'n' and the maximum divisor value 'm'. This results in a time complexity of O(n*m).

Space Complexity

O(1) – The provided algorithm iteratively checks divisors and calculates a sum. It doesn't create any auxiliary data structures like lists, arrays, or hash maps to store intermediate results. The algorithm only uses a few variables to store the current divisor and the sum of the quotients. Therefore, the space used remains constant regardless of the input list of numbers, denoted as N, and the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to solve this problem is to use a method similar to guessing a number in a number-guessing game. Instead of checking every possible divisor one by one, we can quickly narrow down the correct divisor by repeatedly guessing and adjusting our guess.

Here's how the algorithm would work step-by-step:

Figure out the range of possible divisors. The smallest possible divisor is 1, and the largest is the biggest number in the input.
Guess a divisor in the middle of this range.
Using this divisor, divide each number in the input and add up the results, rounding each result up to the nearest whole number.
If the sum is greater than the threshold, it means our divisor guess was too small. Adjust the range to exclude divisors smaller than our guess.
If the sum is less than or equal to the threshold, it means our divisor guess was too big or just right. Adjust the range to exclude divisors larger than our guess.
Repeat steps 2-5, each time guessing the middle of the new range, until the range contains only one number. This number is the smallest divisor that satisfies the condition.

Code Implementation

import math

def find_smallest_divisor(numbers, threshold):
    left_boundary = 1
    right_boundary = max(numbers)

    while left_boundary < right_boundary:
        middle_divisor = (left_boundary + right_boundary) // 2
        
        sum_of_divisions = 0
        for number in numbers:
            sum_of_divisions += math.ceil(number / middle_divisor)

        # Divisor is too small; need to increase it.
        if sum_of_divisions > threshold:

            left_boundary = middle_divisor + 1

        else:
            # Divisor is too large or just right;
            right_boundary = middle_divisor

    # leftBoundary now equals the smallest divisor.
    return left_boundary

Big(O) Analysis

Time Complexity

O(n log m) – The algorithm uses binary search to find the smallest divisor within a range. The search space for the divisor is from 1 to the maximum value (m) in the input array nums. The binary search takes O(log m) iterations. In each iteration, we iterate through the input array nums of size n to calculate the sum of divisions. The division and rounding operation within the loop takes constant time. Thus, each iteration of the binary search takes O(n) time. Therefore, the overall time complexity is O(n log m), where n is the length of the nums array and m is the maximum value in the nums array.

Space Complexity

O(1) – The algorithm utilizes a fixed number of variables, such as storing the lower and upper bounds of the divisor range and the sum of division results, regardless of the size of the input array. No auxiliary data structures like arrays, lists, or hash maps are created to store intermediate values during the computation. The space required remains constant, independent of the input array size N. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty nums array	Return 1 because any divisor will result in a sum of 0, which is likely less than or equal to the threshold.
Null nums array	Throw an IllegalArgumentException or return -1, depending on specified error handling.
Threshold is extremely small (e.g., 1)	The smallest divisor will likely be the sum of all elements in nums if the result of dividing by one is greater than 1.
Threshold is extremely large (much larger than the sum of nums)	The optimal divisor will likely be 1, potentially improving performance by quickly converging in the binary search.
nums array contains a single very large number and a small threshold	The divisor must be at least as large as the large number to satisfy the threshold, ensuring we handle potential integer overflow concerns.
nums array contains very large numbers, potentially leading to integer overflow during intermediate calculations	Use long data type for intermediate sums to prevent integer overflow issues during calculations.
nums array contains all identical numbers	The sum will be nums.length * ceil(number/divisor) and the binary search needs to converge efficiently based on this simplified formula.
No valid divisor exists (e.g., threshold is 0 or very small, and nums contains large numbers)	Return -1 if the binary search range exhausts without finding a suitable divisor, indicating that no solution exists.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the `nums` array and the `threshold` value?
Is it guaranteed that a divisor satisfying the condition will always exist, or should I handle cases where no such divisor is found?
Can the `nums` array be empty?
Is the threshold value guaranteed to be a positive integer?
Could you clarify the rounding behavior? Should I use the ceiling function to round up the results of the divisions?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the smallest possible divisor, which is 1.
For the current divisor, go through each number in the given list.
Divide each number in the list by the current divisor and round the result up to the nearest whole number.
Add all the rounded-up results together to get a total sum.
Check if the total sum is less than or equal to the given target.
If the total sum is less than or equal to the target, you've found a divisor that works. Since we started with the smallest possible divisor and worked our way up, this must be the smallest divisor that works, so we're done.
If the total sum is greater than the target, increase the divisor by 1 and repeat the process from step 2.

Code Implementation

import math

def find_smallest_divisor(numbers, threshold):
    smallestDivisor = 1

    while True:
        totalSum = 0

        for number in numbers:
            # Round up the division result and add to the total sum
            totalSum += math.ceil(number / smallestDivisor)

        # Check if the total sum satisfies the threshold condition
        if totalSum <= threshold:
            return smallestDivisor

        # Increment the divisor to find the smallest that satisfies condition
        smallestDivisor += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Figure out the range of possible divisors. The smallest possible divisor is 1, and the largest is the biggest number in the input.
Guess a divisor in the middle of this range.
Using this divisor, divide each number in the input and add up the results, rounding each result up to the nearest whole number.
If the sum is greater than the threshold, it means our divisor guess was too small. Adjust the range to exclude divisors smaller than our guess.
If the sum is less than or equal to the threshold, it means our divisor guess was too big or just right. Adjust the range to exclude divisors larger than our guess.
Repeat steps 2-5, each time guessing the middle of the new range, until the range contains only one number. This number is the smallest divisor that satisfies the condition.

Code Implementation

import math

def find_smallest_divisor(numbers, threshold):
    left_boundary = 1
    right_boundary = max(numbers)

    while left_boundary < right_boundary:
        middle_divisor = (left_boundary + right_boundary) // 2
        
        sum_of_divisions = 0
        for number in numbers:
            sum_of_divisions += math.ceil(number / middle_divisor)

        # Divisor is too small; need to increase it.
        if sum_of_divisions > threshold:

            left_boundary = middle_divisor + 1

        else:
            # Divisor is too large or just right;
            right_boundary = middle_divisor

    # leftBoundary now equals the smallest divisor.
    return left_boundary

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty nums array	Return 1 because any divisor will result in a sum of 0, which is likely less than or equal to the threshold.
Null nums array	Throw an IllegalArgumentException or return -1, depending on specified error handling.
Threshold is extremely small (e.g., 1)	The smallest divisor will likely be the sum of all elements in nums if the result of dividing by one is greater than 1.
Threshold is extremely large (much larger than the sum of nums)	The optimal divisor will likely be 1, potentially improving performance by quickly converging in the binary search.
nums array contains a single very large number and a small threshold	The divisor must be at least as large as the large number to satisfy the threshold, ensuring we handle potential integer overflow concerns.
nums array contains very large numbers, potentially leading to integer overflow during intermediate calculations	Use long data type for intermediate sums to prevent integer overflow issues during calculations.
nums array contains all identical numbers	The sum will be nums.length * ceil(number/divisor) and the binary search needs to converge efficiently based on this simplified formula.
No valid divisor exists (e.g., threshold is 0 or very small, and nums contains large numbers)	Return -1 if the binary search range exhausts without finding a suitable divisor, indicating that no solution exists.