Explained: Allocate minimum number of pages

   October 28, 2022

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:

  1. 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.
  2. 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.
  3. 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.

array to Allocate minimum number of pages

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

Our number line will be,

our number range

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

binary search mid element

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).

Coding 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;
    }
};
Best 100+ Python Projects with source code

Also Read:

Share:

Author: Ayush Purawr