The problem statement is ->

We want to scan N documents using two scanners. If S1 and S2 are the time taken by the scanner 1 and scanner 2 to scan a single document, find the minimum time required to scan all the N documents.

Example:-

S1 = 2, S2 = 4, N = 2

Output: 4

Explanation: Here we have two possibilities. Either scan both documents in scanner 1 or scan one document in each scanner. In both the cases time required is 4.

I came up with a solution where we find all the combinations and insert them into the set. The minimum value will be the first element in the set.

The problem is the solution will have time complexity of O(n), but the accepted time complexity is O(logn).

I am thinking on the lines of binary search but can't come up with a solution.

What should be the approach?

CodePudding user response：

If you could scan a fraction of a document, the fastest way would be to scan N*S2/(S1 S2) documents in scanner 1, and N*S1/(S1 S2) documents in scanner 2. And if these are not integers, you must round one of them up and one of them down, which gives you just two possibilities to check. This is O(1), not O(log n).

CodePudding user response：

Well, I'm sharing the O(log n) approach. With binary search on ans / time, we could find the optimal time.

For binary search, we need upper bound & lower bound. Let's assume lower bound as 0. Now we need to find out the upper bound.

What will be the minimum time required if we scan all the documents in one scanner. It will be min (S1,S2) * N, right? Note: here we are not using other scanner which could scan documents while another one is busy. So min(S1,S2) * N will be our upper bound.

We've got our bounds,

Lower bound = 0

Upper bound = min(S1,S2) * N

Now do BS on time, take a mid & check how many documents can be scanned with scanner 1 scanner 2 within mid time. Whenever total scanned documents get >= N then mid could be ans .

You can check BS from here - https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/