Given an array arr[] of integers, where each element arr[i] represents the…
2025
Given an array arr[] of integers, where each element arr[i] represents the number of pages in the i-th book. You also have an integer k representing the number of students. The task is to allocate books to each student such that:
Each student receives at least one book.
Each student is assigned a contiguous sequence of books.
No book is assigned to more than one student.
All books must be allocated.
The objective is to minimize the maximum number of pages assigned to any student. In other words, out of all possible allocations, find the arrangement in which the student who receives the most pages still receives as few pages as possible. If it is not possible to allocate books to all students, print -1.
Note: Test cases are generated such that the answer always fits in a 32-bit integer.
Input format:
The first line contains two integers n and k — the number of books and the number of students.
The second line contains n space-separated integers arr[0] … arr[n-1] — the number of pages in each book.
Output format:
Print a single integer — the minimum possible value of the maximum pages assigned to any student, or -1 when no valid allocation exists.
Examples:
Input:
4 2
12 34 67 90
Output:
113
Explanation: The allocation can be done in the following ways:
=> [12] and [34, 67, 90], maximum pages = 191
=> [12, 34] and [67, 90], maximum pages = 157
=> [12, 34, 67] and [90], maximum pages = 113
The split [12, 34, 67] and [90] gives the smallest maximum assigned to any student, which is 113.
Input:
3 5
15 17 20
Output:
-1
Explanation: Since there are more students than books, it is impossible to give each student a book.
Constraints:
n = arr.size()
1 ≤ arr.size() ≤ 106
1 ≤ arr[i], k ≤ 104
Show answer & explanation
Concept
When a yes/no test feasible(x) is monotonic over an ordered range of candidate values — false for every value strictly below some threshold and true at that threshold and for every value above it — the smallest x for which feasible(x) is true can be located by binary search over the range of values itself, instead of over array positions. This technique is called binary search on the answer, or parametric search. It applies whenever the quantity to be minimized is the parameter of a monotonic feasibility test that can be evaluated quickly.
Application
Here the parameter is limit, a candidate ceiling on the number of pages any one student may receive. Define feasible(limit) to mean: the books can be cut into at most k contiguous blocks with no block exceeding limit pages. Raising limit can never increase the number of blocks needed, so feasible is false strictly below a threshold and true at that threshold and above — exactly the monotonic shape binary search requires.
Rule out the impossible case first. Every student must receive at least one book, so when k is greater than n = arr.size() no allocation exists and the answer is -1. Once k ≤ n holds, testing for at most k blocks is equivalent to testing for exactly k blocks: any split into fewer than k blocks can be cut further at book boundaries until exactly k non-empty blocks remain, and because every page count is positive such a cut never raises any block's total.
Fix the search range. A single book must fit inside one student's share, so the ceiling can never be smaller than max(arr[i]); one student taking every book gives the largest ceiling ever needed, sum(arr[i]). The answer therefore lies in the range [max(arr), sum(arr)]. Hold this sum and the values lo, hi and mid in a 64-bit type: with up to 106 books of up to 104 pages, sum(arr) can reach 1010, which overflows a 32-bit integer in C, C++ and Java even though the final answer is promised to fit in 32 bits.
Evaluate feasible(limit) greedily in one pass. Walk the books from left to right carrying a running total and extend the current block as far as limit allows: only when adding the next book would push that total above limit do you close the block and start a new one with that book. Report whether the resulting block count is at most k. Extending every block maximally is optimal because cutting earlier than necessary leaves at least as many books for the blocks that follow and so can never reduce the block count; and every single book fits on its own, because limit is never smaller than max(arr).
Binary search the range. While lo is at most hi, take mid = lo + (hi - lo) / 2 with integer floor division — write // in Python and Math.floor in JavaScript — a form that also avoids overflow when lo + hi would exceed the accumulator. If feasible(mid) holds, record mid as the best answer so far and continue in [lo, mid - 1]; otherwise continue in [mid + 1, hi]. The value recorded when the loop ends is the minimum possible maximum.
Account for the cost. Each feasibility test is a single linear scan over the n books, and the binary search runs at most 1 + ⌊log2(sum - max + 1)⌋ such tests, so the total is O(n · (1 + log(sum - max + 1))) time — bounded by O(n log(sum + 1)) — and O(1) extra space, which is fast enough for arrays of up to a million books. The leading 1 matters because sum - max is 0 when the array holds a single book: the range then holds a single candidate, and testing that one candidate still costs a full scan.
Cross-check
Take arr[] = [12, 34, 67, 90] with k = 2. Here max(arr) = 90 and sum(arr) = 203, so the search starts on the range [90, 203] and each candidate ceiling is tested with the greedy scan.
Candidate limit | Greedy blocks | Block count | Feasible |
|---|---|---|---|
146 | [12, 34, 67], [90] | 2 | Yes |
117 | [12, 34, 67], [90] | 2 | Yes |
103 | [12, 34], [67], [90] | 3 | No |
110 | [12, 34], [67], [90] | 3 | No |
113 | [12, 34, 67], [90] | 2 | Yes |
111 | [12, 34], [67], [90] | 3 | No |
112 | [12, 34], [67], [90] | 3 | No |
The search closes on 113: a ceiling of 113 lets the first block hold 12 + 34 + 67 = 113 exactly and leaves 90 for the second student, while a ceiling of 112 forces the first block to stop at 12 + 34 = 46 and then needs three students. So 113 is the smallest maximum that any two-student allocation can achieve, which matches the expected output. The case arr[] = [15, 17, 20] with k = 5 never reaches the binary search at all: the k > n guard fires because five students cannot each receive one of only three books, so the answer is -1.