समस्या
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.
सीमाएँ
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
उदाहरण
इनपुट:
times = [2, 3]
target = 5
अपेक्षित आउटपुट:
expected = 6इनपुट:
std::vector<long long> times = {2, 3};
long long target = 5;
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long[] times = new long[] {2, 3};
long target = 5;
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
इनपुट:
times = [4]
target = 3
अपेक्षित आउटपुट:
expected = 12इनपुट:
std::vector<long long> times = {4};
long long target = 3;
अपेक्षित आउटपुट:
long long expected = 12;इनपुट:
long[] times = new long[] {4};
long target = 3;
अपेक्षित आउटपुट:
long expected = 12;व्याख्या
One machine completes its third item at 3 × 4 = 12 seconds.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
For any chosen time, you can count how many items all machines together would finish by then.
संकेत 2
The answer is the earliest time where that produced count reaches the target.
संकेत 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
अपेक्षित जटिलता
O(n log T) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।