Given an integer array nums and an integer threshold, find the smallest positive integer divisor such that: After dividing every element of nums by divisor, rounding each result up, and adding all results, the final sum is less than or equal to threshold.
In simple words, for every number num, use ceil(num / divisor), then add all those values. Return the smallest divisor that keeps this sum within the threshold.
The problem guarantees that an answer always exists.
Example 1
Input: nums = [1, 2, 5, 9], threshold = 6
Output: 5
Explanation: Dividing by 5 yields 1 + 1 + 1 + 2 = 5, which is less than or equal to 6. A divisor of 4 yields 1 + 1 + 2 + 3 = 7, which exceeds the threshold. Thus, 5 is the smallest valid divisor.
Example 2
Input: nums = [44, 22, 33, 11, 1], threshold = 5
Output: 44
Explanation: Dividing by 44 yields 1 + 1 + 1 + 1 + 1 = 5, which exactly equals the threshold. Any smaller divisor makes the first term larger than 1, increasing the sum beyond 5.
Brute Force Approach
The most direct idea is to try every possible divisor one by one. The smallest divisor can be 1. The largest useful divisor can be the maximum value in the array, because dividing every number by that value will make each rounded-up result equal to 1. For each divisor, calculate the rounded-up sum. The first divisor whose sum is less than or equal to the threshold is the answer.
This works because divisors are checked in increasing order, so the first valid one is definitely the smallest valid one.
Algorithm
First, find the largest value in the array. This is used as the upper limit because a divisor larger than the maximum value is not needed.
Try every divisor from
1to the largest value. This checks possible answers from smallest to largest.For each divisor, calculate the sum of
ceil(num / divisor)for every number. This tells whether the divisor keeps the total within the threshold.If the sum is less than or equal to the threshold, return that divisor immediately because it is the first valid divisor found.
If the current sum becomes greater than the threshold while calculating, stop checking that divisor early because it has already failed.
Dry Run
Find the Smallest Divisors Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: bool isSumSmallEnough(vector<int>& nums, int divisor, int threshold) { // This stores the sum after rounded-up divisions. int total = 0; for (int num : nums) { total += (num + divisor - 1) / divisor; // If total already crosses the threshold, // this divisor cannot be a valid answer. if (total > threshold) { return false; } } // The divisor works only when the final sum // stays within the allowed threshold. return total <= threshold; }public: /* Finds the smallest divisor by checking every possible divisor one by one. */ int smallestDivisor(vector<int>& nums, int threshold) { // No useful divisor needs to be larger than this value. int maxValue = *max_element(nums.begin(), nums.end()); for (int divisor = 1; divisor <= maxValue; divisor++) { // The first valid divisor is the smallest one, // because divisors are checked in increasing order. if (isSumSmallEnough(nums, divisor, threshold)) { return divisor; } } return maxValue; }};// Driver code startsint main() { vector<int> nums = {1, 2, 5, 9}; int threshold = 6; Solution obj; cout << obj.smallestDivisor(nums, threshold) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x max(nums)), N is the length of array, because every divisor from 1 to the maximum value may be tried, and each check iterates over the full array.
Space Complexity: O(1), because constant space is used.
Optimal Approach
The key pattern is hidden in how the divisor affects the sum. If the divisor is small, each number gets divided by a small value, so the rounded-up results are larger. This can make the sum too big.
If the divisor is large, each number gets divided by a large value, so the rounded-up results become smaller. This makes it easier to stay within the threshold.
So the answers form a pattern like this:
false, false, false, true, true, true
The first true position is the smallest valid divisor. Binary search is used to find exactly that first valid position.
Algorithm
Check Edge Cases:
Calculate the total sum of all elements (
totalSum) and identify the maximum value (maxElement).If
threshold >= totalSum, return1because divisor1already satisfies the threshold.If
threshold == array length, returnmaxElementbecause each element must contribute exactly1to meet the minimum possible sum.
Set
lowto1because the divisor must be a positive integer, and1is the smallest possible divisor.Set
highto the maximum value in the array because this divisor makes every element contribute at most1, so a valid answer must exist by this point.Pick the middle divisor
midand num = nums[mid] and calculate the rounded-up sum using(num + mid - 1) / mid. This formula gives ceiling division without using floating-point numbers.If the sum is less than or equal to the threshold,
midis valid. Movehightomidbecause a smaller valid divisor may still exist on the left side.Otherwise,
midis too small because the sum is too large. Movelowtomid + 1because all divisors up tomidcannot be the answer.When
lowandhighmeet, returnlowbecause it is the smallest divisor that satisfies the threshold.
Dry Run
Find the Smallest Divisors Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: bool canDivideWithinThreshold(vector<int>& nums, int divisor, int threshold) { // This stores the sum made by the current divisor. int total = 0; for (int num : nums) { total += (num + divisor - 1) / divisor; // Once total is too large, this divisor has failed. if (total > threshold) { return false; } } // A divisor is valid only if its final sum // does not go beyond the threshold. return total <= threshold; }public: /* Finds the smallest divisor using binary search over the possible divisor values. */ int smallestDivisor(vector<int>& nums, int threshold) { long long totalSum = 0; int high = 0; for (int num : nums) { totalSum += num; high = max(high, num); } // If threshold >= total sum, divisor 1 is sufficient. if (threshold >= totalSum) { return 1; } // If threshold equals array length, each number must contribute 1, requiring max element. if (threshold == static_cast<int>(nums.size())) { return high; } // The divisor cannot be smaller than 1. int low = 1; while (low < high) { // mid is the divisor being tested in this round. int mid = low + (high - low) / 2; // If mid works, try to find an even smaller divisor. if (canDivideWithinThreshold(nums, mid, threshold)) { high = mid; } else { // If mid fails, every smaller divisor will also fail. low = mid + 1; } } return low; }};// Driver code startsint main() { vector<int> nums = {1, 2, 5, 9}; int threshold = 6; Solution obj; cout << obj.smallestDivisor(nums, threshold) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x log2(max(nums))), N is the length of array, and we perform binary search on our answer range which is 1 to max(nums) taking complexity of log(max(nums)) and each check iterates over full nums.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
If the threshold is equal to or greater than the total sum of all elements in the array without any division, the smallest possible divisor is simply 1.
Be the first to add a comment.