Book Allocation Problem

Last Updated on July 5, 2023 by Mayank Dham

Book Allocation Problem

In this article, we will address the problem of Book Allocation. We will begin by presenting a straightforward and intuitive approach to tackling the problem. Subsequently, we will explore a more efficient solution using the binary search technique.
Let’s start our article with the problem statement.

What is Book Allocation Problem

Given an integer array called ‘pages’, where each ‘pages[i]’ represents the number of pages in the ‘i-th’ book, and a total of ‘m’ students, the objective is to allocate all the books among the students.
Allocate books in a way such that:

• Each student gets at least one book.
• Each book should be allocated to a student.
• Book allocation should be in a contiguous manner.

The task is to distribute the books among ‘m’ students in such a way that the maximum number of pages assigned to any student is minimized.

Analysis

• The objective is to minimize the maximum number of pages assigned to any student during the allocation process.
• If the maximum number of pages assigned to a student is denoted by ‘x’, then the number of pages assigned to each student must be less than or equal to ‘x’.
• It is necessary to assign at least one book to every student, meaning that no student should be left without any assigned books.
• Furthermore, all books must be allocated, ensuring that no book is left unassigned.
• The allocation should be done in a contiguous manner. For instance, if three books need to be allocated to a student from the ‘pages[]’ array, such as {10, 20, 30, 40}, valid allocations could be {10, 20, 30} and {20, 30, 40}. However, an allocation like {10, 30, 40} would not be valid since it is not contiguous.

Brute Force Algorithm to Find the Book Allocation Problem

• Let N be the number of books and M the number of students.
• Let’s see the algorithm for all other cases where M<=N:
• In order to address these scenarios, we will explore the range of possible values for the maximum number of pages that can be assigned to a student.
• The minimum value must be greater than 0, as each student needs to be assigned at least one book.
• The maximum number of pages that can be assigned to a student is equal to the sum of all the pages in the array. This occurs when all the books are assigned to a single student.
• Hence, the range of possible values for the maximum number of pages is (0, the sum of all values in the ‘pages’ array]. We use an open interval for 0 to account for the requirement of assigning at least one book to every student. Therefore, the interval becomes [1, sum of values in the ‘pages’ array].

How to check if it is possible to allocate the books such that the maximum number of pages assigned to any student is x?

• Begin by initializing the student count to 1.
• Allocate books to a student repeatedly until the sum of the assigned pages is less than ‘x’.
• If, at any stage, the number of pages assigned to a student exceeds ‘x’, assign the current book to the next student and increment the student count.
• If the student count exceeds ‘M’, return false.
• Finally, if the student count is equal to ‘M’, return true.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;


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;
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += pages[i];
    }
    
    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;
}

Time Complexity:The time complexity of the above code is O(n * Sum), where ‘n’ represents the number of integers in the ‘pages’ array, and ‘Sum’ denotes the sum of all the elements in the ‘pages’ array.
The code utilizes two nested loops, one iterating up to the value of ‘Sum’ and the other up to ‘n’. Therefore, the time complexity is *O(n Sum).**

Space Complexity: The space complexity of the above code is indeed O(1) since it uses constant space. The code does not require any additional data structures or dynamically allocated memory that scales with the input size. Hence, the space complexity is constant.

Binary Search Approach To Find Book Allocation Problem

In this approach, we utilize binary search to efficiently search for the optimal solution. It offers improved time efficiency compared to the previously discussed approach.

The algorithm leverages the concept of binary search to reduce the time complexity by narrowing down the search space to [1, Sum of pages array]. By dividing the search space in half at each iteration, the algorithm achieves improved efficiency.

Algorithm To Find Book Allocation Problem

• We initialize ‘start’ as 0 and ‘end’ as the sum of all pages.
• The next step is to calculate the middle value as ‘mid’ using the formula (start + end) / 2.
• We then check if it is feasible to allocate the books in such a way that the number of pages assigned to each student is less than or equal to ‘mid’.
• If it is possible, we update the minimum answer found so far and set ‘end’ as ‘mid – 1’. This is because we are searching for the minimum value of the maximum number of pages, so we reduce our search space for the next iteration to [start, mid – 1] in order to find a value less than ‘mid’.
• If it is not possible to allocate the books with the maximum pages equal to ‘mid’, we update ‘start’ as ‘mid + 1’. Since it is impossible for any value less than ‘mid’ to be feasible, we update the search space to [mid + 1, end].
• We repeat the above steps until ‘start’ is less than or equal to ‘end’.

Code Implementation:

#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];
    }
    
    //Initialize start with 0 and end with sum.
    int start = 0, end = sum;
    int result = INT_MAX;
    
    //Traverse until start <= end , binary search.
    while (start <= end) {
    
        /* 
        	Checking if it is possible to distribute books by using 
        	mid as current maximum 
        */
        int mid = start + (end - start) / 2;
        if (isPossible(pages, n, m, mid)) {
            result = min(result, mid); 
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return result;
}
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;
}

Time Complexity: The time complexity of the aforementioned algorithm is O(N * log(Sum)), where ‘N’ represents the number of integers in the ‘pages’ array, and ‘Sum’ signifies the sum of all the elements in the ‘pages’ array.

For each value of ‘mid’, there is an iteration loop of size ‘N’, and the binary search operation has a time complexity of log(Sum). Hence, the overall time complexity is O(N * log(Sum)).

Space Complexity: The space complexity of the above algorithm is O(1) since it utilizes constant space. The algorithm does not require any additional data structures or dynamically allocated memory that scales with the input size. Thus, the space complexity remains constant.

Conclusion
In this article, we explored the utilization of binary search in solving the book allocation problem. We began by examining the naive approach and then proceeded to the more efficient binary search approach. Additionally, we delved into the implementation of this algorithm in popular programming languages and conducted a complexity analysis of the approaches discussed.

FAQs related to Book Allocation Problem

Q1. What is the concept of binary search?
Binary search is a technique used to efficiently search for a specific value within a sorted list or array. It follows a divide-and-conquer approach by repeatedly dividing the search space in half and narrowing down the possibilities until the desired value is found or determined to be absent.

Q2. In the book allocation problem, what is the time complexity of the naive approach?
The naive approach for the book allocation problem has a time complexity of O(n * Sum), where ‘n’ represents the number of elements in the array, and ‘Sum’ represents the sum of all the elements in the array.

Q3. What is the time complexity of the binary search approach for the book allocation problem?
The time complexity of the binary search approach for the book allocation problem is O(n * log(Sum)), where ‘n’ is the number of elements in the array and ‘Sum’ is the sum of all the elements in the array.

Q4. What technique does the binary search algorithm utilize?
The binary search algorithm utilizes the divide-and-conquer technique. It repeatedly divides the search space in half and focuses on the relevant portion where the target value is most likely to be found.

Q5. What are the requirements for applying the binary search algorithm?
The binary search algorithm requires that the list or array on which it is applied must be sorted in ascending or descending order. This allows the algorithm to efficiently divide the search space and eliminate half of the remaining possibilities at each iteration.