What Is A Book Allocation Problem

Are you looking for a feasible method to resolve the Book allocation problem?

• Are you confused on how to apply its methods?

If yes, we have come up with the best and easiest solution to fix the book allocation problem. 

This is an advanced programming problem that you will often come across in your competitive programming or exams. However, many programmers use different approaches to resolve the problem, which obviously creates confusion. 

Thus this makes it worth reading this post!!

Here, we have come up with a complete explanation of what the book allocation problem is and what is the best method to resolve it. So, let’s get this guide started.

Problem Statement:

In this problem, you will be provided with the number of pages of “N” books. Additionally, there is m number of students to whom the given books are required to be assigned. All the given books are arranged in the increasing order of the pages. 

Each student needs to be assigned consecutive books. You need to write a code to return the maximum number of pages a student read which also needs to be a minimum.

Now that you have got an idea of what the book allocation problem is, let’s consider an example to get a better hold of the problem.

You are given the following array of parameters:

m= 2 and pages={ 12, 34, 67 90}

The output of the program will be 113.

Let’s understand how:

In the first scenario, the pages will be divided into the following format:

{12} and {34, 67, 90} 

In this case, the maximum number of pages will be allotted to number 2 which is 191 pages.

In the second scenario, the pages will be divided into the following format:

{12, 34} and {67, 90}

In this case, the maximum number of pages will be allotted to number 2 which is 157 pages.

In the third scenario, the pages will be divided into the following format:

{12, 34, 67} and {90}

In this case, the maximum number of pages will be allotted to number 1 which is 113 pages.

Out of all these cases, option 3 provides a minimum of pages which is 113 pages.

Approach To Solve Book Allocation Problem

By now you must be aware of the book allocation problem. Let’s begin with the solution of this problem.

The basic idea is to use a binary search to solve the problem. We initialize the value for the number of pages as the present maximum and minimum. Initialize minimum as 0 and maximum as the sum of all the pages. 

In case the current mid is the solution, then we will have to look in the lower half otherwise find it in the upper half. 

Now, one of the questions that everyone asks is how can you check if the mid value is feasible or not. More importantly, we will have to check if the pages can be assigned to students in a way that the number does not exceed the current value.

For this, you will have to assign pages to each student sequentially and ensure that the current number assigned should not exceed the value. However, in case the number of students increases more than m, the solution is not feasible. 

Algorithm 

If you are still not sure how to resolve this problem with binary search, check out the algorithm mentioned below:

• To begin with, initialize start=0 and end= total of all the pages
• Calculate middle- (start+end)/2
• Now, check if you can allocate books in a way that the number of pages allocated to every student is less than or equal to the middle.
• If it is possible then, 
• Update the answer you have found so far and initialize end= middle -1.
• Now that we require the minimum value of the maximum number of pages, set the end as middle-1. Now the space search will become [start, middle-1].
• Else,
• You need to update start= middle-1. This is because if you are not able to allocate the books with maximum pages for values till the middle, you will not be able to find it for any value less than the middle. Therefore, the search space will look like [Middle+1, end].
• Follow the same set of steps until the start is equal to or less than the end.

Various Approaches

The book allocation problem can be solved via various approaches such as the Brute Force Approach & the Binary Search Approach.

To better understand the approaches, let’s check out the below example of solving the Book Allocation Problem via the Brute Force Approach –

Implementation In C++

/* C++ code for Book Allocation problem to find the minimum value of the maximum
number of pages*/
#include <bits/stdc++.h>

using namespace std;
/*function to check if it is possible to allocate the books such that the
maximum number of pages assigned to any student is numPages*/
bool isPossible(int pages[], int n, int m, int numPages) {
    int cntStudents = 1;
    int curSum = 0;
    for (int i = 0; i < n; i++) {
        if (pages[i] > numPages) {
            return false;
        }
        if (curSum + pages[i] > numPages) {
            /* Increment student count by '1'*/
            cntStudents += 1;
            /* assign current book to next student and update curSum */
            curSum = pages[i];
            /* If count of students becomes greater than given no. of students, return False*/
            if (cntStudents > m) {
                return false;
            }
        } else {
            /* Else assign this book to current student and update curSum */
            curSum += pages[i];
        }
    }
    return true;
}
int allocateBooks(int pages[], int n, int m) {
    /* If number student is more than number of books */
    if (n < m) {
        return -1;
    }
    /* Count total number of pages */
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += pages[i];
    }
    /* Check for every possible value */
    for (int numPages = 1; numPages <= sum; numPages++) {
        if (isPossible(pages, n, m, numPages)) {
            return numPages;
        }
    }
    return -1;
}
int main() {
    int n = 4;
    int m = 2;
    int pages[] = {10, 20, 30, 40};
    cout << "The minimum value of the maximum number of pages in book allocation is: " << allocateBooks(pages, n, m) << endl;
}

Complexity Analysis For The Solution

To determine how feasible the solution of the problem is, it is a must to analyze its complexity. Here, we are going to discuss the space and time complexity of the solution.

Time complexity: The time complexity of this algorithm is O(n*sum). Here, the sum is the total of all the pages and n depicts the number of integers in the array. Here, we will use two nested loops. Therefore, the complexity of the algorithm is calculated as O(n*sum).

Space complexity: Now, the space complexity of this solution is O(1). This is because a constant space is being used.

Important Points To Keep In Mind

While you are solving the book allocation problem, there are certain things that you will have to keep in mind. Check out the pointers below.

• You need to assign at least one book to each student. Therefore, there must be no allocation where no student is assigned a book.
• It should be ensured that no book is left out. In simple words, each and every book must be assigned.

Other than this, you will have to allocate all the books in a contiguous manner. 

Conclusion

Book allocation problem is one of the advanced problems that most people are asked about in their technical interviews including BFS algorithm. Therefore, preparing for such problems is important before you go for an interview.

To resolve this issue, we will suggest the use of the binary search method. There are other approaches as well that you can use to resolve the issue including the brute force method. However, it may be less feasible than binary search.

Also Read – Reason Why Mean Stack Is The Preferred Option In Development?