Given the number of jars required by N junior chefs for keeping ingredients which they may take in any order, find out the minimum number of jars required so as to ensure every chef can complete his recipe. It is to be noted that once a chef completes his recipe, he puts back the jars for reuse by other chefs.
- The worst case would be when each chef has taken one less than the number of jars required to complete their dish and no jar is left. So one more than that number of jars is the required answer.
- In the worst case, the number of jars taken is \sum x - N. So, the required answer is \sum x- N+1 as by that last extra jar, at least one chef shall complete his dish and put back jars used by him for others.
Quick Explanation said it all.
We need to think what can be the worst case, where the maximum number of jars are used and yet chefs are unable to complete their dishes. It happens when all chefs are one short of their jar requirement.
Since once any chef completes his dish, the jars are available for reuse. So, the worst case shall not have any chef’s dish already completed. So, now, we need to find the maximum number of jars such that each chef’s dish isn’t ready, but using a maximum number of jars.
That’s it. For chef requiring x jars, we can block x-1 jars. So, the Maximum number of jars such that no dish is complete is \sum (x-1). Now, to break this deadlock, we need one more jar. Hence, the required number of jars is \sum x - N+1.
Click to view
PS: Another one of my quick editorial xD. @vijju123, you might want to have a look here.
Time complexity is O(N) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.