Geek is organizing a party at his house. For the party, he needs exactly N (N ? 103) donuts for the guests. Geek decides to order the donuts from a nearby restaurant, which has L chefs and each chef has a rank R. A chef with rank R can make 1 donut in the first R minutes, 1 more donut in next 2R minutes, 1 more donut in 3R minutes, and so on. The task is to find the minimum time in which all the orders will be fulfilled.
Examples:
Input: N = 10, L = 4, rank[] = {1, 2, 3, 4}
Output: 12
Explanation: Chef with rank 1, can make 4 donuts in time 1 + 2 + 3 + 4 = 10 mins
Chef with rank 2, can make 3 donuts in time 2 + 4 + 6 = 12 mins
Chef with rank 3, can make 2 donuts in time 3 + 6 = 9 mins
Chef with rank 4, can make 1 donuts in time = 4 minutes
Total donuts = 4 + 3 + 2 + 1 = 10 and
Maximum time taken by all = 12 minutes.Input: N = 8, L = 8, rank[] = {1, 1, 1, 1, 1, 1, 1, 1}
Output: 1
Explanation: As all chefs are ranked 1, so each chef can make 1 donuts 1 min.
Total donuts = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 and min time = 1 minute
Naive approach: To solve the problem follow the below idea:
The idea is to linearly search in the time line, the answer will be the minimum time for which chefs can make N donuts
Follow the steps to solve the problem:
- We will iterate from 1 to 10000000 then check for every ith minute if chefs can make all of the N donuts
- For every ith minute, count the number of donuts each chef can make.
- Sum up all the donuts made by all the chef and check whether it is greater or equal to N
- We can easily calculate that the answer will lie between 10000000 for the given constraints.
Time Complexity: O(N * T) where T is the value of the time range.
Auxiliary Space: O(1)
Minimum Time to fulfill orders using Binary Search:
To solve the problem follow the below idea:
We can do a binary search on time line to find the minimum time taken by all to make all the donuts.
Follow the steps to solve the problem:
- As the answers lie between 1 and 10000000 so we will take 2 boundaries, left boundary is 1 and the right boundary is 10000000
- Now, we will check the midpoint of the current search space. mid = (left + right) / 2.
- Now let’s say X is the number of donuts all chefs can make at mid time.
- If X ? N then, mid may be the answer and we will reduce the search space by assigning the right boundary to mid – 1.
- When X < N, the answer will be greater than mid, so we can reduce the search space by assigning the left boundary to mid+1.
- The minimum time can be received at the end of the traversal.
Below is the implementation for the above approach:
C++
// C++ Code to implement the approach.#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to fulfill N orders in 'mid' timebool isPossible(int p, vector<int>& cook, int n, int mid){ int cnt = 0; for (int i = 0; i < n; i++) { // For each cook count the pratas int c = 0; int time = mid; // Time taken to cook each // pratas by ith cook int perpratas = cook[i]; while (time > 0) { time = time - perpratas; if (time >= 0) { c += 1; perpratas += cook[i]; } } cnt += c; if (cnt >= p) return true; } return false;}// Function to find the minimum time required// to fulfill the ordersint findMinTime(int n, vector<int>& arr, int l){ // write your code here int s = 0, e = 10000007; int mid, ans = -1; // Loop to implement binary search while (s <= e) { mid = (s + e) / 2; if (isPossible(n, arr, l, mid)) { ans = mid; e = mid - 1; } else { s = mid + 1; } } return ans;}// Driver codeint main(){ int N = 10, L = 4; vector<int> rank = { 1, 2, 3, 4 }; // Function call cout << findMinTime(N, rank, L); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.Scanner; class GFG { public static boolean isPossible(int p, int[] cook, int n, int mid) { int cnt = 0; for (int i = 0; i < n; i++) { // For each cook count the pratas int c = 0; int time = mid; // Time taken to cook each // pratas by ith cook int perpratas = cook[i]; while (time > 0) { time = time - perpratas; if (time >= 0) { c += 1; perpratas += cook[i]; } } cnt += c; if (cnt >= p) return true; } return false; } // Function to find the minimum time required // to fulfill the orders static int findMinTime(int n, int[] arr, int l) { // write your code here int s = 0, e = 10000007; int mid, ans = -1; // Loop to implement binary search while (s <= e) { mid = (s + e) / 2; if (isPossible(n, arr, l, mid)) { ans = mid; e = mid - 1; } else { s = mid + 1; } } return ans; } public static void main(String[] args) { int N = 10, L = 4; int[] rank = new int[]{ 1, 2, 3, 4 }; // Function call System.out.println(findMinTime(N, rank, L)); }}// This code is contributed by ksam24000 |
Python3
# python3 Code to implement the approach.# Function to check if it is possible# to fulfill N orders in 'mid' timedef isPossible(p, cook, n, mid): cnt = 0 for i in range(0, n): # For each cook count the pratas c = 0 time = mid # Time taken to cook each # pratas by ith cook perpratas = cook[i] while (time > 0): time = time - perpratas if (time >= 0): c += 1 perpratas += cook[i] cnt += c if (cnt >= p): return True return False# Function to find the minimum time required# to fulfill the ordersdef findMinTime(n, arr, l): # write your code here s, e = 0, 10000007 mid, ans = 0, -1 # Loop to implement binary search while (s <= e): mid = (s + e) // 2 if (isPossible(n, arr, l, mid)): ans = mid e = mid - 1 else: s = mid + 1 return ans# Driver codeif __name__ == "__main__": N = 10 L = 4 rank = [1, 2, 3, 4] # Function call print(findMinTime(N, rank, L)) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approachusing System;class GFG { // Function to check if it is possible // to fulfill N orders in 'mid' time static bool isPossible(int p, int[] cook, int n, int mid) { int cnt = 0; for (int i = 0; i < n; i++) { // For each cook count the pratas int c = 0; int time = mid; // Time taken to cook each // pratas by ith cook int perpratas = cook[i]; while (time > 0) { time = time - perpratas; if (time >= 0) { c += 1; perpratas += cook[i]; } } cnt += c; if (cnt >= p) return true; } return false; } // Function to find the minimum time required // to fulfill the orders static int findMinTime(int n, int[] arr, int l) { // write your code here int s = 0, e = 10000007; int mid, ans = -1; // Loop to implement binary search while (s <= e) { mid = (s + e) / 2; if (isPossible(n, arr, l, mid)) { ans = mid; e = mid - 1; } else { s = mid + 1; } } return ans; } // Driver code public static void Main(string[] args) { int N = 10, L = 4; int[] rank = { 1, 2, 3, 4 }; // Function call Console.Write( findMinTime(N, rank, L)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JS code to implement the approach // Function to check if it is possible // to fulfill N orders in 'mid' time function isPossible(p, cook, n, mid) { let cnt = 0; for (let i = 0; i < n; i++) { // For each cook count the pratas let c = 0; let time = mid; // Time taken to cook each // pratas by ith cook let perpratas = cook[i]; while (time > 0) { time = time - perpratas; if (time >= 0) { c += 1; perpratas += cook[i]; } } cnt += c; if (cnt >= p) return true; } return false; } // Function to find the minimum time required // to fulfill the orders function findMinTime(n, arr, l) { // write your code here let s = 0, e = 10000007; let mid, ans = -1; // Loop to implement binary search while (s <= e) { mid = Math.floor((s + e) / 2); if (isPossible(n, arr, l, mid)) { ans = mid; e = mid - 1; } else { s = mid + 1; } } return ans; } // Driver code let N = 10, L = 4; let rank = [1, 2, 3, 4]; // Function call document.write(findMinTime(N, rank, L));// This code is contributed by Potta Lokesh </script> |
Output
12
Time Complexity: O(N*logN).
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
