Book Club Reading Plan
Your book club picked a novel and set a deadline: everyone finishes in days days. You know the page count of every chapter. You will read the chapters in order, never stop in the middle of one, and read at least one chapter on each reading day you use.
You want a daily page limit you can stick to every day. A low limit is easier on your evenings, but too low and you miss the deadline. What is the lowest limit that still works?
Your task
Write dailyPageLimit(chapters, days). Split chapters, in order, into at most days consecutive groups (each day reads one group). Return the smallest possible value of the largest group's page total.
Finishing early is fine, so using fewer than days days is allowed.
dailyPageLimit(chapters: int[], days: int) → int
Examples
chapters = [12, 30, 8, 25, 15, 10] days = 3
42
Read 12 + 30 = 42, then 8 + 25 = 33, then 15 + 10 = 25. The busiest day is 42. With a limit of 41 you would need 4 days: 12 | 30 + 8 | 25 + 15 | 10. The average, 100 / 3 ≈ 34, is not achievable.
chapters = [40, 10, 10, 10] days = 2
40
The 40-page chapter cannot be split, so the limit is at least 40. And 40 works: day 1 reads it, day 2 reads the other 30 pages.
Constraints
- 1 ≤ chapters.length ≤ 10,000
- 1 ≤ chapters[i] ≤ 10,000
- 1 ≤ days ≤ 10,000
Start with brute force
Try every limit from the longest chapter upward, running the greedy day count each time, and stop at the first one that fits. Or try every way to cut the chapters into groups.
Cutting is exponential. Counting up limits is O(n × S), where S can be up to 100,000,000 pages: far too many tries. Binary search on the limit needs about 27 tries, each a single O(n) pass.
Hints
0 of 4 shown- Hint 1
Forget finding the best split. If someone handed you a limit, say 41 for the first example, could you quickly tell whether 3 days are enough?
- Hint 2
Yes: read greedily. Keep adding chapters to today until the next one would push you over the limit, then start a new day. Count the days. Reading as much as allowed each day can never make you need more days.
- Hint 3
If a limit works, every larger limit works too. So the limits form a row of "too low" followed by "works". You want the first "works". What is the smallest limit worth trying, and the largest?
- Hint 4
Binary search the limit between
max(chapters)(you must fit the longest chapter) andsum(chapters)(everything in one day). For each middle limit, run the greedy day count. If it fits indays, keep it and search lower; otherwise search higher.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Finding the best split directly is hard. Checking a given limit is easy, and the answers are monotonic: once a limit works, every bigger one works. So binary search on the answer, using the easy check.
Trace [12, 30, 8, 25, 15, 10] with 3 days. The limit is somewhere between 30 (the longest chapter) and 100 (the total):
lo = 30,hi = 100,mid = 65. Greedy: 12 + 30 + 8 = 50 | 25 + 15 + 10 = 50. 2 days, fits.hi = 65.mid = 47. 12 + 30 = 42 | 8 + 25 = 33 | 15 + 10 = 25. 3 days, fits.hi = 47.mid = 38. 12 | 30 + 8 = 38 | 25 | 15 + 10. 4 days, too many.lo = 39.mid = 43. Same split as 47: 3 days, fits.hi = 43.mid = 41. 12 | 30 + 8 | 25 + 15 | 10. 4 days.lo = 42.mid = 42. 12 + 30 | 8 + 25 | 15 + 10. 3 days, fits.hi = 42. Nowlo = hi = 42.
Start lo at the longest chapter, not at 1. Below that the greedy check is meaningless: a 30-page chapter can never fit under a 20-page limit, yet the loop above would happily put it on its own day and count it.
function dailyPageLimit(chapters, days) {
// how many days does a given limit need, reading greedily?
const daysNeeded = (limit) => {
let count = 1, today = 0;
for (const pages of chapters) {
if (today + pages > limit) { count++; today = 0; } // start a new day
today += pages;
}
return count;
};
let lo = Math.max(...chapters);
let hi = chapters.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (daysNeeded(mid) <= days) hi = mid; // works: try lower
else lo = mid + 1; // too low
}
return lo;
}def daily_page_limit(chapters, days):
# how many days does a given limit need, reading greedily?
def days_needed(limit):
count, today = 1, 0
for pages in chapters:
if today + pages > limit:
count += 1 # start a new day
today = 0
today += pages
return count
lo, hi = max(chapters), sum(chapters)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid # works: try lower
else:
lo = mid + 1 # too low
return loRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.