Problem Statement: You are given an array of integers ‘arr’ and an integer i.e. a threshold value ‘limit’. Your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division’s result is less than or equal to the given threshold value.
Examples
Example 1:
Input Format: N = 5, arr[] = {1,2,3,4,5}, limit = 8
Result: 3
Explanation: We can get a sum of 15(1 + 2 + 3 + 4 + 5) if we choose 1 as a divisor.
The sum is 9(1 + 1 + 2 + 2 + 3) if we choose 2 as a divisor. Upon dividing all the elements of the array by 3, we get 1,1,1,2,2 respectively. Now, their sum is equal to 7 <= 8 i.e. the threshold value. So, 3 is the minimum possible answer.
Example 2:
Input Format: N = 4, arr[] = {8,4,2,3}, limit = 10
Result: 2
Explanation: If we choose 1, we get 17 as the sum. If we choose 2, we get 9(4+2+1+2) <= 10 as the answer. So, 2 is the answer.
Point to remember:
- While dividing the array elements with a chosen number, we will always take the ceiling value. And then we will consider their summation. For example, 3 / 2 = 2.
Observation:
- Minimum possible divisor: We can easily consider 1 as the minimum divisor as it is the smallest positive integer.
- Maximum possible divisor: If we observe, we can conclude the maximum element in the array i.e. max(arr[]) is the maximum possible divisor. Any number > max(arr[]), will give the exact same result as max(arr[]) does. This divisor will generate the minimum possible result i.e. n(1 for each element), where n = size of the array.
With these observations, we can surely say that our answer will lie in the range
[1, max(arr[])].
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Naive Approach(Brute-force):
The extremely naive approach is to check all possible divisors from 1 to max(arr[]). The minimum number for which the result <= threshold value, will be our answer.
Algorithm:
- We will run a loop(say d) from 1 to max(arr[]) to check all possible divisors.
- To calculate the result, we will iterate over the given array using a loop. Within this loop, we will divide each element in the array by the current divisor, d, and sum up the obtained ceiling values.
- Inside the outer loop, If result <= threshold: We will return d as our answer.
- Finally, if we are outside the nested loops, we will return -1.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int smallestDivisor(vector<int>& arr, int limit) {
int n = arr.size(); //size of array.
//Find the maximum element:
int maxi = *max_element(arr.begin(), arr.end());
//Find the smallest divisor:
for (int d = 1; d <= maxi; d++) {
//Find the summation result:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += ceil((double)(arr[i]) / (double)(d));
}
if (sum <= limit)
return d;
}
return -1;
}
int main()
{
vector<int> arr = {1, 2, 3, 4, 5};
int limit = 8;
int ans = smallestDivisor(arr, limit);
cout << "The minimum divisor is: " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int smallestDivisor(int[] arr, int limit) {
int n = arr.length; //size of array.
//Find the maximum element:
int maxi = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
maxi = Math.max(maxi, arr[i]);
}
//Find the smallest divisor:
for (int d = 1; d <= maxi; d++) {
//Find the summation result:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += Math.ceil((double)(arr[i]) / (double)(d));
}
if (sum <= limit)
return d;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int limit = 8;
int ans = smallestDivisor(arr, limit);
System.out.println("The minimum divisor is: " + ans);
}
}
import math
def smallestDivisor(arr, limit):
n = len(arr) # size of array
maxi = max(arr)
# Find the smallest divisor
for d in range(1, maxi+1):
# Find the summation result
sum = 0
for i in range(n):
sum += math.ceil(arr[i] / d)
if sum <= limit:
return d
return -1
arr = [1, 2, 3, 4, 5]
limit = 8
ans = smallestDivisor(arr, limit)
print("The minimum divisor is:", ans)
function smallestDivisor(arr, limit) {
let n = arr.length; // size of array
let maxi = Math.max(...arr); // find the maximum element
// Find the smallest divisor
for (let d = 1; d <= maxi; d++) {
// Find the summation result
let sum = 0;
for (let i = 0; i < n; i++) {
sum += Math.ceil(arr[i] / d);
}
if (sum <= limit)
return d;
}
return -1;
}
let arr = [1, 2, 3, 4, 5];
let limit = 8;
let ans = smallestDivisor(arr, limit);
console.log("The minimum divisor is:", ans);
Output:The minimum divisor is: 3
Complexity Analysis
Time Complexity: O(max(arr[])*N), where max(arr[]) = maximum element in the array, N = size of the array.
Reason: We are using nested loops. The outer loop runs from 1 to max(arr[]) and the inner loop runs for N times.
Space Complexity: O(1) as we are not using any extra space to solve this problem.
Optimal Approach
Algorithm / Intuition
Optimal Approach(Using Binary Search):
We are going to use the Binary Search algorithm to optimize the approach.
The primary objective of the Binary Search algorithm is to efficiently determine the appropriate half to eliminate, thereby reducing the search space by half. It does this by determining a specific condition that ensures that the target is not present in that half.
Now, we are not given any sorted array on which we can apply binary search. Upon closer observation, we can recognize that our answer space, represented as [1, max(arr[])], is actually sorted. Additionally, we can identify a pattern that allows us to divide this space into two halves: one consisting of potential answers and the other of non-viable options. So, we will apply binary search on the answer space.
Algorithm:
- If n > threshold: If the minimum summation i.e. n > threshold value, the answer does not exist. In this case, we will return -1.
- Next, we will find the maximum element i.e. max(arr[]) in the given array.
- Place the 2 pointers i.e. low and high: Initially, we will place the pointers. The pointer low will point to 1 and the high will point to max(arr[]).
- Calculate the ‘mid’: Now, inside the loop, we will calculate the value of ‘mid’ using the following formula:
mid = (low+high) // 2 ( ‘//’ refers to integer division) - Eliminate the halves based on the summation of division results:
We will pass the potential divisor, represented by the variable ‘mid’, to the ‘sumByD()‘ function. This function will return the summation result of the division values.- If result <= threshold: On satisfying this condition, we can conclude that the number ‘mid’ is one of our possible answers. But we want the minimum number. So, we will eliminate the right half and consider the left half(i.e. high = mid-1).
- Otherwise, the value mid is smaller than the number we want. This means the numbers greater than ‘mid’ should be considered and the right half of ‘mid’ consists of such numbers. So, we will eliminate the left half and consider the right half(i.e. low = mid+1).
- Finally, outside the loop, we will return the value of low as the pointer will be pointing to the answer.
The steps from 3-4 will be inside a loop and the loop will continue until low crosses high.
Note: Please make sure to refer to the video and try out some test cases of your own to understand, how the pointer ‘low’ will be always pointing to the answer in this case. This is also the reason we have not used any extra variable here to store the answer.
The algorithm for sumByD() is given below:
sumByD(arr[], div):
arr[] -> the given array, div -> the divisor.
- We will run a loop to iterate over the array.
- We will divide each element by ‘div’, and consider the ceiling value.
- With that, we will sum up the ceiling values as well.
- Finally, we will return the summation.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int sumByD(vector<int> &arr, int div) {
int n = arr.size(); //size of array
//Find the summation of division values:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += ceil((double)(arr[i]) / (double)(div));
}
return sum;
}
int smallestDivisor(vector<int>& arr, int limit) {
int n = arr.size();
if (n > limit) return -1;
int low = 1, high = *max_element(arr.begin(), arr.end());
//Apply binary search:
while (low <= high) {
int mid = (low + high) / 2;
if (sumByD(arr, mid) <= limit) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low;
}
int main()
{
vector<int> arr = {1, 2, 3, 4, 5};
int limit = 8;
int ans = smallestDivisor(arr, limit);
cout << "The minimum divisor is: " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int sumByD(int[] arr, int div) {
int n = arr.length; //size of array
//Find the summation of division values:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += Math.ceil((double)(arr[i]) / (double)(div));
}
return sum;
}
public static int smallestDivisor(int[] arr, int limit) {
int n = arr.length; //size of array.
if(n > limit) return -1;
//Find the maximum element:
int maxi = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
maxi = Math.max(maxi, arr[i]);
}
int low = 1, high = maxi;
//Apply binary search:
while (low <= high) {
int mid = (low + high) / 2;
if (sumByD(arr, mid) <= limit) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int limit = 8;
int ans = smallestDivisor(arr, limit);
System.out.println("The minimum divisor is: " + ans);
}
}
import math
def sumByD(arr, div):
n = len(arr) # size of array
# Find the summation of division values
total_sum = 0
for i in range(n):
total_sum += math.ceil(arr[i] / div)
return total_sum
def smallestDivisor(arr, limit):
n = len(arr)
if n > limit:
return -1
low = 1
high = max(arr)
# Apply binary search
while low <= high:
mid = (low + high) // 2
if sumByD(arr, mid) <= limit:
high = mid - 1
else:
low = mid + 1
return low
arr = [1, 2, 3, 4, 5]
limit = 8
ans = smallestDivisor(arr, limit)
print("The minimum divisor is:", ans)
function sumByD(arr, div) {
let n = arr.length; // size of array
let sum = 0;
for (let i = 0; i < n; i++) {
sum += Math.ceil(arr[i] / div);
}
return sum;
}
function smallestDivisor(arr, limit) {
let n = arr.length;
if(n > limit) return -1;
let low = 1;
let high = Math.max(...arr);
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (sumByD(arr, mid) <= limit) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
let arr = [1, 2, 3, 4, 5];
let limit = 8;
let ans = smallestDivisor(arr, limit);
console.log("The minimum divisor is:", ans);
Output:The minimum divisor is: 3
Complexity Analysis
Time Complexity: O(log(max(arr[]))*N), where max(arr[]) = maximum element in the array, N = size of the array.
Reason: We are applying binary search on our answers that are in the range of [1, max(arr[])]. For every possible divisor ‘mid’, we call the sumByD() function. Inside that function, we are traversing the entire array, which results in O(N).
Space Complexity: O(1) as we are not using any extra space to solve this problem.
Video Explanation
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article