Hello everyone in this article, we will discuss a very famous DSA problem Allocate minimum number of pages(https://practice.geeksforgeeks.org/problems/allocate-minimum-number-of-pages0937/1). It’s a GeeksforGeeks hard-level problem. We will discuss the problem statement, approach, and code one after another.

**Problem Explanation**

If we look at the problem statement carefully, we have 3 restrictions in this question:

- Each book will be allocated to exactly one student, which means we can not divide one book’s pages into two or three, or more parts, one book will be read by only one student.
- Each student has to be allocated at least one book, which means we have to give at least one book to each student, we can’t leave any student any book.
- Allotment of books should be contiguous i.e., let’s say we have 4 books {10,20,30,40} in this situation we cannot give any student in order {10, 30} because allocation can not be discontinuous.

Keeping these restrictions in mind, we have to divide books in such an order that each student gets a minimum number of pages to read.

**Solution and Approach**

Now that we have understood the problem statement and the restrictions we can move towards a solution approach.

This problem is solved with the help of binary search! That’s right, binary search will be used, sometimes the binary search can be used on answers.

In this approach, we will not sort the array of books because we have to make the distribution contiguous, because of which we can not change the order of books given to us in question.

The basic idea of binary search is to initialize two pointers one from the beginning and one from the end of the array find mid and compare mid with the given target and move the pointer accordingly.

For this question let’s think we have a number line starting from 0 to the sum of all pages in the array because the maximum a student can read is all books.

Let’s consider this array shown above and the number of students is 2.

Our number line will be,

Now, we will apply binary search on this number line:

We have our mid as 50, now we will check if we have our maximum limit of pages is 50 i.e. maximum number of pages a student can read is 50, do we satisfy the criteria,

student 1 = 10 + 20 but if we add 30 in this our total sum will be 60, which is not allowed as per our assumption.

Student 2 = 30 now if we add 40 in this out total sum will be 70, which again doesn’t satisfy the criteria.

From this example, we realized we have to set our bar to more than 50.

Again applying binary search we will get mid = 75, which will satisfy the condition but we need to find the minimum number of pages, so we keep finding the mid until our (low < high).

**Cod**ing solution to Allocate minimum number of pages:

### Python Code for Allocate minimum number of pages:

class Solution: #Function to find minimum number of pages. def findPages(self,A, N, M): #code here if M>N:return -1 def binarySearch(mid): pageSum = 0 student = 1 for i in range(N): if pageSum+A[i]<=mid: pageSum+=A[i] else: student+=1 if student>M or A[i]>mid: return False pageSum = A[i] return True begin = max(A) end = sum(A) res = -1 while begin<=end: mid = (begin+end)//2 if binarySearch(mid): res = mid end = mid-1 else: begin = mid+1 return res

**C++ code for Allocate minimum number of pages**:

class Solution { public: //functoin to find if the mid is a valid number of not bool isvalid(int A[], int N, int M, int max) { int student =1; int sum =0; for(int i=0;i<N;i++) { sum+=A[i]; //if sum crosses max we will add a student if(sum>max) { student +=1; sum = A[i]; } //at any point if number of student becomes more than given student we return false if(student >M) return false; } return true; } //Function to find minimum number of pages. int findPages(int A[], int N, int M) { if(N<M) return -1; int high = 0; for(int i=0;i<N;i++) high += A[i]; int res=-1; int low = A[N-1]; //applying binary search while(low<=high) { int mid = low + (high-low)/2; if(isvalid(A,N,M, mid) == true) { res = mid; high = mid-1; } else low = mid+1; } return res; } };

**Also Read:**

- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
- HackerRank Day 12 Solution in Python: Inheritance