Problem
All machines start at time 0 and work independently. A machine with time t finishes one item after t seconds, another after 2t seconds, and so on. Find the earliest whole second when their combined production reaches the target.
Implement factory_machines(times, target).
Input
times: Seconds needed for one item on each machine.
target: The number of completed items required.
Output
Return the minimum elapsed seconds.
Constraints
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
Examples
Input:
times = [2, 3]
target = 5
Expected output:
expected = 6Input:
std::vector<long long> times = {2, 3};
long long target = 5;
Expected output:
long long expected = 6;Input:
long[] times = new long[] {2, 3};
long target = 5;
Expected output:
long expected = 6;Explanation
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
Input:
times = [4]
target = 3
Expected output:
expected = 12Input:
std::vector<long long> times = {4};
long long target = 3;
Expected output:
long long expected = 12;Input:
long[] times = new long[] {4};
long target = 3;
Expected output:
long expected = 12;Explanation
One machine completes its third item at 3 × 4 = 12 seconds.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
For any chosen time, you can count how many items all machines together would finish by then.
Hint 2
The answer is the earliest time where that produced count reaches the target.
Hint 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
Expected complexity
O(n log T) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.