Minimum daily reading pace to finish a textbook

Model one chapter. Chapters are read in order, and one day never covers two chapters. On each day the student reads min(remaining pages of the current chapter, x). So a chapter with p pages takes exactly ceil(p / x) days, and the chapters do not affect each other. The total is

days_needed(x) = sum(ceil(p / x) for p in pages).

Feasibility. Every chapter needs at least one day, so if days < n no x works and the answer is -1. If days >= n, then x = max(pages) finishes every chapter in one day, so an answer always exists and it is at most max(pages).

Brute force. Try x = 1, 2, ..., max(pages) and return the first x with days_needed(x) <= days. That is O(n · max(pages)). It is correct but too slow when pages go up to 10^9. Say it out loud, then improve it.

Binary search on the answer. days_needed(x) never increases as x grows: each ceil(p / x) is non-increasing in x. So the predicate days_needed(x) <= days is false for small x and true from some point on. Binary search for the first x where it is true, over [1, max(pages)].

Invariant. Keep lo as a value known (or assumed) to be too small, or the left edge, and hi as a value known to work. While lo < hi, test mid = (lo + hi) // 2. If mid works, the answer is <= mid, so set hi = mid. If not, the answer is > mid, so set lo = mid + 1. The loop ends with lo == hi equal to the smallest working x.

Tighter bounds (optional). The answer is at least ceil(sum(pages) / days), because each day reads at most x pages. That lower bound cuts a few iterations but does not change the complexity.

Early exit in the check. Stop summing as soon as the running total passes days. This keeps the check fast and avoids building huge sums.

from typing import List, Optional


def days_needed(pages: List[int], x: int, limit: Optional[int] = None) -> int:
    """Days to read every chapter at most x pages a day.

    Stops early once the total passes `limit` (when given).
    """
    total = 0
    for p in pages:
        total += (p + x - 1) // x  # ceil(p / x) without floats
        if limit is not None and total > limit:
            return total
    return total


def min_pages_per_day_brute(pages: List[int], days: int) -> int:
    """O(n * max(pages)) baseline for small inputs."""
    if not pages:
        return 0
    if days < len(pages):
        return -1
    for x in range(1, max(pages) + 1):
        if days_needed(pages, x) <= days:
            return x
    return max(pages)


def min_pages_per_day(pages: List[int], days: int) -> int:
    """Smallest x so the student finishes all chapters within `days` days.

    Returns -1 when it is impossible (fewer days than chapters).
    """
    if not pages:
        return 0
    if days < len(pages):
        return -1
    lo = max(1, (sum(pages) + days - 1) // days)  # each day reads <= x pages
    hi = max(pages)                               # one day per chapter
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(pages, mid, days) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo


if __name__ == "__main__":
    assert min_pages_per_day([5, 3, 4], 5) == 3      # 2 + 1 + 2 = 5 days at x=3
    assert min_pages_per_day([5, 3, 4], 3) == 5
    assert min_pages_per_day([5, 3, 4], 2) == -1
    assert min_pages_per_day([10], 3) == 4
    assert min_pages_per_day([10], 100) == 1
    assert min_pages_per_day([1, 1, 1], 3) == 1
    assert min_pages_per_day([10**9], 1) == 10**9
    assert min_pages_per_day([10**9, 10**9], 4) == 5 * 10**8
    import random
    for _ in range(500):
        arr = [random.randint(1, 30) for _ in range(random.randint(1, 6))]
        d = random.randint(1, 40)
        assert min_pages_per_day(arr, d) == min_pages_per_day_brute(arr, d)
    print("ok")

• days_needed: O(n) time, O(1) space.
• min_pages_per_day: O(n · log(max(pages))) time. The search range has at most max(pages) values, and each step runs one O(n) check. O(1) extra space.
• Brute force: O(n · max(pages)) time, O(1) space.

• pages = [5, 3, 4], days = 5 → 3 (x=3 takes 2 + 1 + 2 = 5 days; x=2 takes 3 + 2 + 2 = 7).
• pages = [5, 3, 4], days = 3 → 5 (one day per chapter needs x = max(pages)).
• pages = [5, 3, 4], days = 2 → -1 (fewer days than chapters).
• pages = [10], days = 3 → 4 (x=3 needs 4 days; x=4 needs 3).
• pages = [10], days = 100 → 1 (lots of slack still means at least 1 page a day).
• pages = [1, 1, 1], days = 3 → 1.
• pages = [10^9], days = 1 → 10^9 (large values; use 64-bit sums outside Python).
• pages = [10^9, 10^9], days = 4 → 5·10^8.
• pages = [], days = 0 → 0 (nothing to read; confirm this edge with the interviewer).

• Return the schedule too. After finding x, walk the chapters and emit (day, chapter, pages_read) for each day. This is O(total days). If days is huge, return one run per chapter instead: (chapter, full_days, last_day_pages).
• A day may continue into the next chapter. If the student reads a fixed x pages a day across chapter borders, the days needed is just ceil(sum(pages) / x), so the answer is ceil(sum(pages) / days) in O(n). If chapters must not be split across days but a day may hold several whole chapters, it becomes the "split array largest sum" problem: binary search on x in [max(pages), sum(pages)] with a greedy packing check.
• Rest days or a fixed schedule. If some days are blocked (exams, travel), only the count of free days matters for this model, so replace days with the number of free days. If capacity varies by day (cap[d] · x), the check becomes a simulation over days, still monotone in x, so the binary search stays.
• Many queries. For many days values on the same pages, sort the queries and note that days_needed(x) is non-increasing. Precompute days_needed only at the O(sqrt(max)) breakpoints where ceil(p / x) changes, or answer each query with its own O(n log M) search when Q is small.
• Streaming chapters. If chapters arrive one by one and you must keep the current minimum x for a fixed days, the answer only grows. Restart the search from the previous answer as the lower bound (lo = prev), which keeps each update cheap in practice.

Mid-level (L4)

• Sees that each chapter costs ceil(p / x) days on its own and writes the brute force.
• Spots that the cost is monotone in x and writes a correct binary search with clean bounds.
• Handles days < n and computes ceil with integers.

Senior (L5)

• States the invariant of the search (hi always works, lo is the smallest candidate) and avoids off-by-one errors without trial and error.
• Adds the early exit in the check and the ceil(sum / days) lower bound, and explains why neither changes correctness.
• Tests edge cases on their own: one chapter, days == n, huge page counts, overflow in other languages.

Staff (L6+)

• Frames it as "binary search on the answer over a monotone predicate" and maps the follow-ups (cross-chapter reading, packing whole chapters, variable capacity) onto the same pattern or a closed form.
• Discusses the schedule output size and when to return a compact form instead.
• Talks about multi-query and streaming versions and what can be reused between calls.