Update appNew update is available. Click here to update.
Last Updated: May 24, 2023
Medium

Book Allocation Problem

Author Shubham Agarwal
10 upvotes

Introduction

In this article, we will solve the problem: Book Allocation. We will start this article with a quite naive and intuitive approach. Then we will proceed toward a more optimal method of the binary search solution. 

Book Allocation Problem

Let’s start our article with the problem statement.

Recommended Topic, Array Implementation of Queue

Problem Statement

You are given an array ‘pages’ of integer numbers. In this array, the ‘pages[i]’ represents the number of pages in the ‘i-th’ book. There are ‘m’ number of students, and the task is to allocate all the books to 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.
     

You have to allocate the books to ‘m’ students such that the maximum number of pages assigned to a student is minimum.

Try to solve this problem on your own before moving on to further discussion here.

Let’s understand the problem statement through an example.

Example

Input

Number of books = 4 and Number of students = 2

pages[] = { 10,20,30,40}

Input

Output

 60

Explanation

All possible ways of book allocation are shown in the below figure-

Output Explanation

The minimum of the maximum number of pages assigned = min{90,70,60} = 60. Hence, the required answer is 60.

Analysis

  • We have to minimize the value of the maximum number of pages assigned to a student during the allocation. 
     
  • If the maximum number of pages assigned to a student in a book allocation is a number x, then the number of pages assigned to every student is less than or equal to x.
     
  • We have to assign at least one book to every student, so there can’t be any allocation such that a student gets no books assigned.
     
  • While allocating the books, no book should be left out. In other words, we have to allocate every book given.
     
  • Allocate in a contiguous manner. Let's say; for example, you have to allocate three books to a student from pages[] = { 10,20,30,40}. Then, the possible allocations can be - {10,20,30} and {20,30,40}. You can’t allocate {10,30,40} as it is not contiguous.

Brute force Approach

Algorithm

Let N be the number of books and M the number of students.

 

In the case of M > N:

  • Simply return -1 as the number of students exceeds the number of books available. According to the given constraints, giving at least one book to each student is impossible.

 

Let’s see the algorithm for all other cases where M<=N:

  • For all of these cases, we will try to find all possible values of the number of pages that can be assigned to a student.
     
  • The minimum value should be greater than 0 (In this problem, you must assign each student at least one book, so the number of pages can't be zero).
     
  • The maximum number of pages will be the sum of the number of pages in all books. (This will happen when you assign all the books to one student).
     
  • The range of the maximum number of pages we obtained is - 
    (0, sum of all the values of pages array]. Open interval on 0 because at least one book needs to be assigned to every student. So, we get the interval [1, sum of pages array].
     

Steps of Algorithm

  • Iterate over all values of the number of pages(say x) ranging from x = 1 to x = sum of elements in the pages array.
     
  • Check if it is possible to allocate the books such that the value of the number of pages assigned to any student is less than or equal to x in each iteration.
     
  • If the maximum number of pages equals x, then return x as the answer. We don’t need to iterate further because the value of x will increase after this. But, we are interested in finding the minimum value of the maximum number of pages that can be allocated.

 

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

  • Initialize the count of students with 1.
     
  • Keep allocating the books to a student until the sum of the pages assigned is less than x.
     
  • If at any point the number of pages assigned to a student exceeds x, then allocate the current book to the next student and increment the count of students.
     
  • If the count for the number of students exceeds M, then return false.
     
  • At the end, if the count of students is equal to M, return true. 

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;
}

Implementation in Java

public class Main {
    /*
    	function to check if it is possible to allocate the books such that the 
    	maximum number of pages assigned to any student is numPages
    */
    static boolean isPossible(int arr[], int n, int m, int curr_min) {
        int cntStudents = 1;
        int curSum = 0;
         // iterate over all the books
        for (int i = 0; i < n; i++) {
             if (arr[i] > curr_min)
                return false;
             if (curSum + arr[i] > curr_min) {
             
                 //Increment student count by '1'
                cntStudents++;
                
                //assign current book to next student and update curSum.
                curSum = arr[i];
                
                //If count of students becomes greater than given no. of students, return False.
                if (cntStudents > m)
                    return false;
            }
            //Else assign this book to current student and update curSum.
            else
                curSum += arr[i];
        }
        return true;
    }

    // method to find minimum number of pages
    static int findPages(int arr[], int n, int m) {
        long sum = 0;
        //If number student is more than number of books.
        if (n < m)
            return -1;
            
        //Count total number of pages.
        for (int i = 0; i < n; i++)
            sum += arr[i];
            
        for (int numPages = 1; numPages <= sum; numPages++) {
            if (isPossible(arr, n, m, numPages)) {
                return numPages;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int arr[] = {10, 20, 30, 40};
        int m = 2; //No. of students
        int n = 4;
        System.out.println("The minimum value of the maximum number of pages in book allocation is: " + findPages(arr, n, m));
    }
}

Implementation in Python

def isPossible(arr, n, m, curr_min):
    cntStudents = 1
    curSum = 0
# iterate over all the books
    for i in range(n):
         if (arr[i] > curr_min):
             return False
        # Increment student count by '1'
         if (curSum + arr[i] > curr_min):
            cntStudents += 1
            # assign current book to next student and update curSum
            curSum = arr[i]
             
            '''
                If count of students becomes greater than
                given no. of students, return False
                update curSum
            '''
            
            if (cntStudents > m):
                return False
         else:
            curSum += arr[i]
    return True
# function to find minimum number pages
def allocateBooks(arr, n, m):
    sum = 0
# If number student is more than number of books
    if (n < m):
        return -1
# Count total number of pages
    for i in range(n):
        sum += arr[i]
        
    
    for numPages in range(1, sum+1):
        ans = isPossible(arr, n, m, numPages)
        if (ans):
            return numPages
    return -1

 
# Number of pages in books
arr = [10, 20, 30, 40]
n = len(arr)
m = 2  # No. of students
print("The minimum value of the maximum number of pages in book allocation is:",
      allocateBooks(arr, n, m))

Output

Output 1

Time Complexity

The time complexity for the above code is O(n*Sum), where ‘n’ is the number of integers in the array ‘pages’ and ‘Sum’ is the sum of all the elements of ‘pages’.

We are using two nested loops of size, ‘Sum’ and ‘n.’ So, the time complexity is O(n*Sum).

Space Complexity

The space complexity of the above code is O(1), as we are using constant space.

Binary Search Approach

For this approach, we have the intuition to use binary search to search for the best possible answer. Also, take less time than the above-discussed approach. 

Algorithm

The idea of this algorithm is to use binary search over the search space [1, Sum of pages array] to improve the time complexity since we are limiting our search space to half each time.

Steps of algorithm

  • We initially have ‘start = 0’ and ‘end = sum of all pages.’
     
  • Then our next step is to find mid = (start+end)/2.
     
  • Then we check if it is possible to allocate books such that the number of pages allocated to each student is less than or equal to mid.
     
  • If possible, then:
    • We update the minimum answer found so far and put end = mid-1.
    • Since we need the minimum value of the maximum number of pages, the end is set as mid-1. We do so to reduce our search space for the next iteration to [start,mid-1] and to get a value less than mid.
       
  • Else 
    • We update start = mid+1. Since it is impossible to allocate the books with maximum pages equal to mid; so it won’t be possible for any value less than mid. So, the search space becomes [mid+1, end].
       
  • Repeat the above steps until start <= end.

Dry Run

Let us see in all the iterations what we get as start, end and mid.

Dry run binary search approach

After this iteration, we will get End = 60-1, that is, End = 59. So, now start > end. Thus, we stop here, and our answer is 60.  

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];
    }
    
    //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;
}

Implementation in Java

public class Main {

  

  /*
  	function to check if it is possible to allocate the books such that the
  	maximum number of pages assigned to any student is numPages
  */

  static boolean isPossible(int arr[], int n, int m, int curr_min) {
    int cntStudents = 1;

    int curSum = 0;


    // iterate over all the books

    for (int i = 0; i < n; i++) {
      if (arr[i] > curr_min) return false;

      if (curSum + arr[i] > curr_min) {
        //Increment student count by '1'

        cntStudents++;

        // assign current book to next student and update curSum.

        curSum = arr[i];

        // If count of students becomes greater than given no. of students, return False.

        if (cntStudents > m) return false;
      } 
      
	//Else assign this book to current student and update curSum.
      else curSum += arr[i];
    }

    return true;
  }

  // method to find minimum number of pages

  static int findPages(int arr[], int n, int m) {
    long sum = 0;

    //If number student is more than number of books.

    if (n < m) return -1;

    //Count total number of pages.

    for (int i = 0; i < n; i++) sum += arr[i];

    //Initialize start with 0 and end with sum.

    int start = 0, end = (int) sum;

    int result = Integer.MAX_VALUE;

    //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) / 2;

     if (isPossible(arr, n, m, mid)) {
        result = mid;

        end = mid - 1;
      } else start = mid + 1;
    }

    return result;
  }

  public static void main(String[] args) {
    int arr[] = { 10, 20, 30, 40 };

    int m = 2; //No. of students

    int n = 4;

    System.out.println(
      "The minimum value of the maximum number of pages in book allocation is: " +
      findPages(arr, n, m)
    );
  }
}

Implementation in Python


import sys

 
# function to check if it is possible to allocate the books 
# such that the maximum number of pages assigned to any student is numPages
def isPossible(pages, n, m, numPages):
    cntStudents = 1
    curSum = 0
    for i in range(n):
        # if a book has more pages than numPages, return False
        if pages[i] > numPages:
            return False
        
        # if the current sum of pages exceeds numPages,
        # assign the current book to the next student and update curSum
        if curSum + pages[i] > numPages:
            cntStudents += 1
            curSum = pages[i]
            
            # if the count of students becomes greater than given no. of students, return False
            if cntStudents > m:
                return False
        else:
            # else assign this book to the current student and update curSum
            curSum += pages[i]
    return True

 
def allocateBooks(pages, n, m):
    # if number of students is more than number of books 
    if n < m:
        return -1
    sum = 0
    for i in range(n):
        sum += pages[i]
    start = 0
    end = sum
    result = sys.maxsize
    # traverse until start <= end , binary search
    while start <= end:
        mid = start + (end - start) // 2
        # checking if it is possible to distribute books by using mid as current maximum
        if isPossible(pages, n, m, mid):
            result = min(result, mid) 
            end = mid - 1
        else:
            start = mid + 1
    return result

 
n = 4
m = 2
pages = [10, 20, 30, 40]
print("The minimum value of the maximum number of pages in book allocation is:", allocateBooks(pages, n, m))

Output

Output 2

Time Complexity

The time complexity for the above algorithm is O(N*log(Sum)). Here ‘N’ is the number of integers in the array ‘pages,’ and ‘Sum’ is the sum of all the elements of ‘pages.’ For every number ‘mid,’ we have an iteration loop of size ‘N,’ and binary search takes ‘log(Sum)’ time. So, that makes the time complexity O(N*log(Sum)).

Space Complexity

The space complexity for the above algorithm is O(1), as we use constant space.

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

What is binary search?

Binary search is an efficient algorithm for finding an item from a sorted list of items by repeatedly dividing the search interval in half. Each comparison allows the algorithm to eliminate half of the remaining possibilities.

For the book allocation problem, what time does the naive approach takes?

The naive approach takes time proportional to the O(n*Sum). Here n is the number of elements in the array, and ‘Sum’ is the sum of elements in the array. 

What is the binary search approach's time complexity for the book allocation problem?

The time complexity of the binary search approach is O(n*log(Sum)). Here n is the number of elements in the array, and ‘Sum’ is the sum of elements in the array.

What technique does the binary search algorithm use?

The binary search algorithm is based on the technique of divide and conquer.

What are the criteria for the application of the binary search algorithm?

The important criterion for applying the binary search algorithm is the list on which we are applying the algorithm must be sorted.

Conclusion

In this article, we learned the application of binary search on the book allocation problem. We started with the naive approach and then moved to the optimal approach of binary search. We also learned about its implementation in popular programming languages and their complexity analysis. 

Check out our articles if you think this blog has helped you enhance your knowledge and want to learn more. Visit our website to read more such blogs. 

  1. Introduction To Binary Search Algorithm 
  2. Searching and Sorting Algorithms 
  3. Implement Linear Search and Binary Search in an Array 
  4. Binary Search Vs Ternary Search  
  5. Ternary Search 

 

For placement preparations, you must look at the problemsinterview experiences, and interview bundles. Enrol in our courses and refer to the mock tests and problems available; look at the Problem Sheets interview experiences, and interview bundle for placement preparations. You can also book an interview session with us.  

Consider our paid courses, however, to give your career a competitive advantage!

Happy Coding!

Previous article
Aggressive Cows
Next article
Maximum triplet sum in Array
Codekaze-June23 India's Biggest Tech Hiring Challenge is LIVE!
Register Now
Go on top