Description
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
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
Approach
The problem is an example of a type of problem where we find what is the max/min that something can be done.
First, we look for whether the problem is requiring to find the maximum or minimum, and also whether the maximum or minimum would give the first possible or impossible value. For this problem, we are looking for the minimum value that satisfies the given requirements.
Therefore, we can search from the minimum value (1), all the way to the maximum value (the maximum value in the given array), using binary search. For the dividing and adding part, I used a helper function to clean up my code.
For each possible value, we will update answer and hence return the answer when the loop has terminated, providing us the minimum value that satisfies the given threshold.
Solution
def calc(nums, div):
total = 0
for num in nums:
#print(num, div, float(num) / div)
n = float(num) / div
total += math.ceil(n)
return total
class Solution(object):
def smallestDivisor(self, nums, threshold):
left = 1
right = max(nums)
ans = -1
while left <= right:
mid = left + (right - left) / 2
if calc(nums, mid) > threshold:
left = mid + 1
else:
ans = mid
right = mid - 1
return ans
