Leetcode 1283 - Find the Smallest Divisor Given a Threshold
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Understanding the problem
The problem statement on LeetCode reads as follows:
Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.
Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
It is guaranteed 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) / 5 = 3.
Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
Plan your solution
One way to solve this problem is to use a binary search algorithm to find the smallest divisor. We can start by setting the left and right pointers to the minimum and maximum values in the array, respectively. Then, we can compute the sum of the divisions and check if it is less than or equal to the threshold. If it is, we can move the left pointer to the middle point between the left and right pointers. On the other hand, if the sum is greater than the threshold, we can move the right pointer to the middle point. We can repeat this process until the left and right pointers meet. This will give us the smallest divisor such that the sum of the divisions is less than or equal to the threshold.
Implement your solution
Now that we have a plan, let’s implement it in Python.
class Solution:
def smallestDivisor(self,nums, threshold):
# Set the left and right pointers to the minimum and maximum values in the array
left, right = min(nums), max(nums)
# While the left pointer is less than the right pointer
while left < right:
# Calculate the middle point between the left and right pointers
mid = (left + right) // 2
# Calculate the sum of the divisions
sum_ = sum((n + mid - 1) // mid for n in nums)
# If the sum is less than or equal to the threshold
if sum_ <= threshold:
# Move the right pointer to the middle point
right = mid
else:
# Move the left pointer to the middle point
left = mid + 1
# Return the left pointer (which is the smallest divisor)
return left
Test your solution
Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Find the Smallest Divisor Given a Threshold” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases. For example, we can test our solution with an array of length 1, an array of length 2, an array of length 3, and so on. We can also test our solution with different values of the threshold parameter. By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Related:
- count complete tree nodes
- count negative numbers in a sorted matrix
- search in rotated sorted array
- find the town judge with code
Related Posts
- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Leetcode 1027 - Longest Arithmetic Subsequence
- Question 1299 on leetcode
- Leetcode 240 - Search a 2D Matrix II
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- advanced-applications-of-binary-search
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 74 - Search a 2D Matrix
- Leetcode 340 - Longest Substring with At Most K Distinct Characters
- Leetcode 300 - Longest Increasing Subsequence
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- a-binary-search-template
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together