Book Allocation Problem
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Allocate minimum number of pages (Book Allocation Problem), Arrays, Binary Search, Brute Force, Time Complexity, Space Complexity, Big O Notation, Loops, Conditional Statements, Subarray, complexity analysis, constraints, greedy algorithm, prefix sum, search space optimization, binary search, Greedy Strategies, Prefix Sums, Problem Solving Techniques.
Book Allocation Problem Problem Statement Given an array arr of integer numbers, where arr[i] represents the number of pages in the i th book. There are m students, and the task is to allocate all the books to the students. The allocation must satisfy the following conditions: 1. Each student gets at least one book. 2. Each book should be allocated to only one student. 3. Book allocation should be in a contiguous manner. Your task is to allocate the books to m students such that the maximum number of pages assigned to any single student is minimized. If it is not possible to allocate the books according to the rules (e.g., if the number of students m is greater than the number of books n), return 1. Input Specification The first line contains an integer n, representing the number of books. The second line contains n space separated integers, representing the array arr of book pages. The third line contains an integer m, representing the number of students. Output Specification Return a single integer: the minimum possible maximum number of pages assigned to a student. Return 1 if allocation is not possible. Constraints 1 <= n <= 10^5 1 <= arr[i] <= 10^9 1 <= m <= n (For valid allocation. If m n, return 1 as per problem statement.) Sample Test Cases Example 1: Input: Output: Explanation: The allocation of books will be 12, 34, 67 | 90. One student gets the first 3 books (total 12 + 34 + 67 = 113 pages) and the other gets the last one (90 pages). The maximum pages assigned to a student is 113, which is the minimum possible maximum. Example 2: Input: Output: Explanation: The allocation of books will be 25, 46 | 28 | 49 | 24. The students receive (25+46=71), (28), (49), (24) pages respectively. The maximum pages assigned to a student is 71, which is the minimum possible maximum. Difficulty Level Medium