Minimum number of items to be delivered
Given N buckets, each containing A[i] items. Given K tours within which all of the items are needed to be delivered. It is allowed to take items from only one bucket in 1 tour. The task is to tell the minimum number of items needed to be delivered per tour so that all of the items can be delivered within K tours.
Conditions : K >= N
Examples:
Input :
N = 5
A[] = { 1, 3, 5, 7, 9 }
K = 10
Output : 3
Explanation:
By delivering 3 items at a time,
Number of tours required for bucket 1 = 1
Number of tours required for bucket 2 = 1
Number of tours required for bucket 3 = 2
Number of tours required for bucket 4 = 3
Number of tours required for bucket 5 = 3
Total number of tours = 10Input :
N = 10
A[] = 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
k = 50
Output : 9
Approach: It is needed to find the minimum number of items per delivery. So, the idea is to iterate from 1 to the maximum value of items in a bucket and calculate the number of tours required for each bucket and find the total number of tours for complete delivery. The first such value with tours less than or equal to K gives the required number.
Algorithm:
Step 1: Create the function “reqdTours” with the input parameters “a” being a vector and “cur” being an integer.
Step 2: Set “cur tours” to 0 at startup.
Step 3: Determine the size of the vector “a” and store it in “n”.
Step 4: Use a for loop to repeatedly iterate through the vector “a” from index 0 to n-1.
a. When the maximum number of items supplied per trip is “cur,” increase “cur tours” by the number of tours necessary to deliver the items in a[i].
Step 5: Return “cur tours”.
Step 6: Create the function “getMin” with the input parameters “a” being a vector and “k” being an integer.
Step 7: Set “n” to the size of the vector “a” and “maxm” to 0.
Step 8: Use a for loop to repeatedly iterate through the vector “a” from index 0 to n-1. a. Replace “maxm” with the highest value that falls between a[i] and maxm.
Step 9: Set “high” to maxm+1 and “low” to 1.
Step 10: Set “ans” to -1 at startup.
Step 11: Start a while loop with condition low +1 is less than high
a. Determine the middle index “mid” by applying the equation mid = low + (high – low) / 2.
b. Use the “a” and “mid” parameters to call the function “reqdTours,” then save the output in the “cur tours” variable.
c. Update “high” to “mid” and “ans” to “high” if “cur tours” is less than or equal to “k”.
d. Update “low” to “mid” if necessary.
Step 12: Give back “ans”.
Below is the implementation of the above idea:
C++
// C++ program to find the minimum numbers of tours required #include <bits/stdc++.h> using namespace std; int reqdTours(vector< int > a, int cur) { int cur_tours = 0; int n = ( int )a.size(); for ( int i = 0; i < n; i++) cur_tours += (a[i] + cur - 1) / cur; return cur_tours; } int getMin(vector< int > a, int k) { int maxm = 0; int n = ( int )a.size(); // find the maximum element in array for ( int i = 0; i < n; i++) maxm = max(a[i], maxm); int low = 1, high = maxm + 1; int ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } // Driver Code int main() { vector< int > a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }; int k = 50; if (getMin(a, k) == -1) cout << "Not Possible" ; else cout << getMin(a, k); } |
Java
// Java program to find the minimum numbers of tours // required import java.io.*; import java.util.*; class GFG { static int reqdTours( int [] a, int cur) { int cur_tours = 0 ; int n = a.length; for ( int i = 0 ; i < n; i++) cur_tours += (a[i] + cur - 1 ) / cur; return cur_tours; } static int getMin( int [] a, int k) { int maxm = 0 ; int n = a.length; // find the maximum element in array for ( int i = 0 ; i < n; i++) maxm = Math.max(a[i], maxm); int low = 1 , high = maxm + 1 ; int ans = - 1 ; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2 ; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } // Driver Code public static void main(String[] args) { int [] a = { 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 , 100 }; int k = 50 ; if (getMin(a, k) == - 1 ) System.out.println( "Not Possible" ); else System.out.println(getMin(a, k)); } } // This code is contributed by Karandeep1234 |
Python3
# Python3 program to find the minimum numbers of tours required def reqdTours(a, cur): cur_tours = 0 n = len (a) for i in range (n): cur_tours + = (a[i] + cur - 1 ) / / cur return cur_tours def getMin(a, k): maxm = 0 n = len (a) # find the maximum element in array for i in range (n): maxm = max (a[i], maxm) low = 1 high = maxm + 1 ans = - 1 # binary search to find the required number of # tours while (low + 1 < high): mid = low + (high - low) / / 2 # reqdTours find the number of tours # required when number of items # needed to be delivered per tour is mid if (reqdTours(a, mid) < = k): high = mid ans = high else : low = mid return ans # Driver Code if __name__ = = '__main__' : a = [ 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 , 100 ] k = 50 if (getMin(a, k) = = - 1 ): print ( "Not Possible" ) else : print (getMin(a, k)) |
C#
// C# code to implement the approach using System; using System.Collections; public class GFG { public static int reqdTours( int [] a, int cur) { int cur_tours = 0; for ( int i = 0; i < a.Length; i++) cur_tours += (a[i] + cur - 1) / cur; return cur_tours; } public static int getMin( int [] a, int k) { int maxm = 0; int n = a.Length; // find the maximum element in array for ( int i = 0; i < n; i++) maxm = Math.Max(a[i], maxm); int low = 1, high = maxm + 1; int ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } public static void Main( string [] args) { int [] a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }; int k = 50; if (getMin(a, k) == -1) Console.Write( "Not Possible" ); else Console.Write(getMin(a, k)); } } |
Javascript
// Javascript program to find the minimum numbers of tours // required function reqdTours(a, cur) { let cur_tours = 0; let n = a.length; for (let i = 0; i < n; i++) cur_tours += ((a[i] + cur - 1) / cur)|0; return cur_tours; } function getMin(a, k) { let maxm = 0; let n = a.length; // find the maximum element in array for (let i = 0; i < n; i++) maxm = Math.max(a[i], maxm); let low = 1, high = maxm + 1; let ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { let mid = (low + (high - low) / 2)|0; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } let a = [ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 ]; let k = 50; if (getMin(a, k) == -1){ console.log( "Not Possible" ); } else { console.log(getMin(a, k)); } // This code is contributed by aadityaburujwale. |
9
Complexity Analysis:
- Time Complexity: O(N * MAX) where N is the total number of elements in the array and MAX is the maximum element in the array.
- Auxiliary Space: O(1)
Efficient Approach:
The maximum number of items that can be delivered per tour is the maximum element in the array. With this information we can use binary search where initially low = 1 and high = maximum element + 1 and find the number of tours required when number of items needed to be delivered per tour is mid where mid = low + (high – low)/2. If it less than or equal to k, then we update answer to mid and set high = mid, otherwise update low to mid.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum numbers of tours required #include <bits/stdc++.h> using namespace std; int reqdTours(vector< int > a, int cur) { int cur_tours = 0; int n = ( int )a.size(); for ( int i = 0; i < n; i++) cur_tours += (a[i] + cur - 1) / cur; return cur_tours; } int getMin(vector< int > a, int k) { int maxm = 0; int n = ( int )a.size(); // find the maximum element in array for ( int i = 0; i < n; i++) maxm = max(a[i], maxm); int low = 1, high = maxm + 1; int ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } // Driver Code int main() { vector< int > a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }; int k = 50; if (getMin(a, k) == -1) cout << "Not Possible" ; else cout << getMin(a, k); } |
Java
// Java program to find the minimum numbers of tours // required import java.io.*; import java.util.*; class GFG { static int reqdTours( int [] a, int cur) { int cur_tours = 0 ; int n = a.length; for ( int i = 0 ; i < n; i++) cur_tours += (a[i] + cur - 1 ) / cur; return cur_tours; } static int getMin( int [] a, int k) { int maxm = 0 ; int n = a.length; // find the maximum element in array for ( int i = 0 ; i < n; i++) maxm = Math.max(a[i], maxm); int low = 1 , high = maxm + 1 ; int ans = - 1 ; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2 ; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } // Driver Code public static void main(String[] args) { int [] a = { 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 , 100 }; int k = 50 ; if (getMin(a, k) == - 1 ) System.out.println( "Not Possible" ); else System.out.println(getMin(a, k)); } } // This code is contributed by Karandeep1234 |
Python3
# Python3 program to find the minimum numbers of tours required def reqdTours(a, cur): cur_tours = 0 n = len (a) for i in range (n): cur_tours + = (a[i] + cur - 1 ) / / cur return cur_tours def getMin(a, k): maxm = 0 n = len (a) # find the maximum element in array for i in range (n): maxm = max (a[i], maxm) low = 1 high = maxm + 1 ans = - 1 # binary search to find the required number of # tours while (low + 1 < high): mid = low + (high - low) / / 2 # reqdTours find the number of tours # required when number of items # needed to be delivered per tour is mid if (reqdTours(a, mid) < = k): high = mid ans = high else : low = mid return ans # Driver Code if __name__ = = '__main__' : a = [ 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 , 100 ] k = 50 if (getMin(a, k) = = - 1 ): print ( "Not Possible" ) else : print (getMin(a, k)) |
C#
// C# code to implement the approach using System; using System.Collections; public class GFG { public static int reqdTours( int [] a, int cur) { int cur_tours = 0; for ( int i = 0; i < a.Length; i++) cur_tours += (a[i] + cur - 1) / cur; return cur_tours; } public static int getMin( int [] a, int k) { int maxm = 0; int n = a.Length; // find the maximum element in array for ( int i = 0; i < n; i++) maxm = Math.Max(a[i], maxm); int low = 1, high = maxm + 1; int ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { int mid = low + (high - low) / 2; // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } public static void Main( string [] args) { int [] a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }; int k = 50; if (getMin(a, k) == -1) Console.Write( "Not Possible" ); else Console.Write(getMin(a, k)); } } |
Javascript
// JavaScript program to find the minimum numbers of tours required function reqdTours(a, cur) { let cur_tours = 0; let n = a.length; for (let i = 0; i < n; i++) { cur_tours += Math.ceil(a[i] / cur); } return cur_tours; } function getMin(a, k) { let maxm = 0; let n = a.length; // find the maximum element in array for (let i = 0; i < n; i++) { maxm = Math.max(a[i], maxm); } let low = 1, high = maxm + 1; let ans = -1; // binary search to find the required number of // tours while (low + 1 < high) { let mid = low + Math.floor((high - low) / 2); // reqdTours find the number of tours // required when number of items // needed to be delivered per tour is mid if (reqdTours(a, mid) <= k) { high = mid; ans = high; } else { low = mid; } } return ans; } // Driver Code let a = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]; let k = 50; if (getMin(a, k) === -1) { console.log( "Not Possible" ); } else { console.log(getMin(a, k)); } // This code is contributed by akashish__ |
9
Complexity Analysis:
- Time Complexity: O(N * log(MAX)) where N is the total number of elements in the array and MAX is the maximum element in the array.
- Auxiliary Space: O(1)