This approach uses binary search to efficiently find the smallest divisor. The possible divisors can range from 1 to the maximum number in the array. For each candidate divisor, divide each number in the array, take the ceiling of the division result, sum it up, and compare against the threshold.
Binary search helps minimize the number of trials by adjusting the divisor range based on whether the threshold condition is met or not for a given divisor.
Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space.
1#include <vector>
2#include <cmath>
3using namespace std;
4
5class Solution {
6public:
7 int smallestDivisor(vector<int>& nums, int threshold) {
8 int left = 1, right = 1000000;
9 while (left < right) {
10 int mid = (left + right) / 2;
11 int sum = 0;
12 for (int num : nums) {
13 sum += (num + mid - 1) / mid;
14 }
15 if (sum > threshold) {
16 left = mid + 1;
17 } else {
18 right = mid;
19 }
20 }
21 return left;
22 }
23};This C++ solution mirrors the logic of C, but uses C++ syntax and features, such as vectors and ranged-based for loops, to iterate over the numbers. It utilizes binary search to adjust the range of divisors based on the sum condition with respect to the threshold.
This method involves a simple linear search from divisor = 1 upwards, incrementally checking each candidate as a divisor. This approach is less efficient compared to binary search but helps understand the problem in a straightforward manner. We calculate the total sum of the divisions for each divisor and stop when the sum is less or equal to the threshold. Ensuring progressively checking divisors until a valid one is found assures correctness.
Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).
1#include <stdio.h>
2#include <math.h>
3
4int smallestDivisor(int* nums, int numsSize, int threshold) {
5 for (int divisor = 1; ; ++divisor) {
6 int sum = 0;
7 for (int i = 0; i < numsSize; ++i) {
8 sum += (nums[i] + divisor - 1) / divisor;
9 }
10 if (sum <= threshold) {
11 return divisor;
12 }
13 }
14}This code initiates a loop to test each divisor starting from 1 upwards until it finds the smallest divisor satisfying the condition. The ceiling of division is calculated with the same integer math trick as before.