Simultaneous Production

Easy
0/40
1 upvote
Asked in company
PhonePe

Problem statement

You are given the number of machines 'N', an array 'M' of length 'N' where 'M[i]' represents the number of days the i-th machine takes to produce one item, and the total number of items 'O' that need to be ordered.


Return the minimum number of days required for all machines working in parallel to complete the order.


For Example : 
Let 'N' = 2, 'M' = [3, 1], 'O' = 5.
Day 1: Machine 2 produces an item
Day 2: Machine 2 produces an item
Day 3: Both Machine 1 and Machine 2 produce an item
Day 4: Machine 2 produces an item
Total items produced = 1 + 1 + 2 + 1 = 5 items.
Therefore, the answer is 4 days.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains three integers, 'N', 'O'.
The second line contains 'N' integers representing the array 'M'.
Output Format : 
Return the minimum number of days required to complete the order.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= 'N' <= 10^5
1 <= 'M[i]' <= 10^9
1 <= 'O' <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2 7
4 5
Sample Output 1 :
14
Explanation of sample input 1 :
There are 2 machines. Machine 1 takes 4 days per item and Machine 2 takes 5 days per item. We need to produce a total of 7 items.
In 14 days:
Machine 1 can produce 14 / 4 = 3 items.
Machine 2 can produce 14 / 5 = 2 items.
Total items produced = 3 + 2 = 5 items. This is not enough. Let's try 15 days.
In 15 days:
Machine 1 can produce 15 / 4 = 3 items.
Machine 2 can produce 15 / 5 = 3 items.
Total items produced = 3 + 3 = 6 items. Still not enough. Let's try 16 days.
In 16 days:
Machine 1 can produce 16 / 4 = 4 items.
Machine 2 can produce 16 / 5 = 3 items.
Total items produced = 4 + 3 = 7 items.
Thus, the minimum number of days required is 16.
Sample Input 2 :
4 15
1 1 1 1
Sample Output 2 :
4
Hint

The problem asks for the minimum number of days. The number of items produced is non-decreasing with the number of days. Which concept comes to mind?

Approaches (1)
Binary Search

Approach:

  • We can perform a binary search on the number of days.
    • The lower bound for the number of days can be 0 (although practically it will be 1)
    • The upper bound can be the maximum production time multiplied by the total number of items.
  • For a given number of days 'D', we can calculate the total number of items that can be produced by all machines working in parallel.
    • For each machine 'i', the number of items it can produce in 'D' days is 'D / M[i]' (integer division).
  • We sum up the number of items produced by all machines.
    • If the total number of items produced is greater than or equal to the required order 'O', it means that the order can be completed in 'D' days or less.
      • So, we try a smaller number of days in the binary search.
    • If the total number of items produced is less than 'O', it means that 'D' days are not enough
      • So, we need to try a larger number of days.
  • We continue the binary search until the lower bound and upper bound converge to the minimum number of days.

Algorithm:

  • Initialize 'low' to 1.
  • Initialize 'high' to max(M) * O.
  • Initialize 'ans' to 'high'.
  • While 'low' is less than or equal to 'high':
    • Calculate 'mid' as (low + high) // 2.
    • Initialize 'total_produced' to 0.
    • Iterate through each machine's production time 'time' in 'M':
      • Add mid // time to 'total_produced'.
    • If 'total_produced' is greater than or equal to 'O':
      • Set 'ans' to 'mid'.
      • Set 'high' to mid - 1.
    • Else:
      • Set 'low' to mid + 1.
  • Return 'ans'.
Time Complexity

O(N * log(max(M) * O)), where 'N' is the number of machines and 'O' is the number of items ordered, and 'max(M)' is the maximum production time of a machine.

The binary search runs for approximately log(max(M) * O) iterations. In each iteration, we iterate through all 'N' machines to calculate the total number of items produced. Thus, the overall time complexity is of the order O(N * log(max(M) * O)).

Space Complexity

O(1).

We are only using a few variables to store the lower bound, upper bound, middle value, total produced items, and the answer. The space used does not depend on the input size. Thus, the overall space complexity is of the order O(1).

Code Solution
(100% EXP penalty)
Simultaneous Production
Full screen
Console