why high is 1000000001?

1 <= newspapers.length <= 10^5

We need more examples in the problem description. Most of the problems I have seen so far have only 1 example each.

Solution should talk about reducing this problem to “Capacity to Ship Packages Within D Days”. The general idea is the same, 1) time to read → weight of package, 2) # of workers → # of days, 3) output min time to read → output min capacity to rent.

We should first map newspapers array to range of possible read times, [max(newspapers), sum(newspapers)], same as in Capacity problem. Then perform binary search on that range, with a helper function to check read_time satisfies input coworkers. This is the same line of reasoning as in Capacity problem, and in the end we reduce to Finding Boundary, to find first read_time with <= input coworkers.

yeah definitely, that problem is the exact same time! thank you for this insight. unfortunately, the solutions are written differently! interesting question nevertheless.

because max newspaper value = 10^4, and max newspaper list length = 10^5, so the max sum = 10^9, adding 1 for bisecting

Can you add JS answers?

As per Test #3, the max size of each list item is 100_000, not 10_000.

Thank you for pointing out. We’ve fixed it.

Regarding the variable “high”

This can be as below, but I guess it’s initialized to default large number for avoiding unnecessary calculation.

```
int high = 0;
for(int v : newspapers){
high += v;
}
```

Similar way low can be as below.

```
int low = Collections.max(newspapers);
```

Yes,

Replacing this

public static boolean check(List newspapers, int coworkers, int val) {

to would make it work

public static boolean feasible(List weights, int d,int maxWeight) {

int reqDays = 1;

int capacity = maxWeight;

int i = 0, n = weights.size();

while (i < n) {

if (weights.get(i) <= capacity) {

capacity -= weights.get(i);

i++;

} else {

reqDays++;

capacity = maxWeight;

}

}

return reqDays <= d;

}

Maybe need a test case to illustrate this. If you just use 10^5 as the upper bound, all of the tests still pass.

Could anyone explain why we have to add 1 to the result at the end? All of the other code is commented except for that portion. Why does the method always have a delta of 1 and requires it to be added in at the end?

lines 26-27: if it is possible to read newspapers in “mid” time, then high is decreased to mid - 1, (equivalently: mid = high + 1). High is not set in any other place. Hence, at the end, high + 1 corresponds to the shortest time in which it is possible to read all newspapers.

Ah - makes sense. Thank you.

Almost similar to Capacity Problem

from typing import List

def newspapers_split(newspapers: List[int], coworkers: int) → int:

# WRITE YOUR BRILLIANT CODE HERE

def condition(time_req) → bool:

curr_time = 0

worker = 1

for n in newspapers:

curr_time+=n

if curr_time > time_req:

worker += 1

curr_time = n

return worker > coworkers

```
mint = max(newspapers)
maxt = sum(newspapers)
low = mint
high = maxt
boundary = mint
while low <= high:
mid = (low + high) // 2
if condition(mid):
low = mid + 1
else:
boundary = mid
high = mid - 1
return boundary
```

if **name** == ‘**main**’:

newspapers = [int(x) for x in input().split()]

coworkers = int(input())

res = newspapers_split(newspapers, coworkers)

print(res)

int low = 0, high = 0x3f3f3f3f;

Why can’t we set low= max(newspapers) and high = sum(newspapers)

- sum of newspapers array is the maximum time that they can spend to read thru all the newspapers, even if they have 100 co-workers, the amount of time they need to spend to read them is the same, isn’t it?
- low is obviously the max of newspaper array