Allocate a minimum number of pages in python

You have given a sorted array of size n which represents the number of pages in n different books and an integer value which denotes the number of students. We are going to distribute the books to every student. You have to find out the minimum value of pages given to the student who has to read a maximum number of pages.

To allocate the books, you have to follow some conditions, which are as follows:

1. You have to allocate a minimum of one book to each student.
2. You have to allocate the books from an array in a continuous way. If the array is [ 23, 50, 70, 95 ], then you can not give one student a book with 23 pages and a book with 95 pages. You have to give in a manner like 23, 50, 70.
3. You have to allocate a particular book to only one student.

Let’s take an example:

Input- [10, 20, 30, 40, 50] and 2

Output-  90

Explanation- We can allocate the books in this ways-

• First case: -
  • student1 : 10 ( total page = 10)
    • student2 : 20, 30, 40, 50 (total page = 140)
    • Max pages allocated : 140
  • Second case: -
    • student1 : 10, 20 ( total page = 30)
    • student2 : 30, 40, 50 (total page = 120)
    • Max pages allocated : 120
  • Third case: -
    • student1 : 10, 20, 30 ( total page = 60)
    • student2 : 40, 50 (total page = 90)
    • Max pages allocated : 90
  • Fourth case: -
    • student1 : 10, 20, 30, 40 ( total page = 100)
    • student2 : 50 (total page = 50)
    • Max pages allocated : 100

So we can see that in the third case, we get the minimum value of maximum pages allocated to a student. Our answer is 90.

Solution: - We shall use the binary search approach to solve this problem. Let’s see the algorithm.

Algorithm:-

Step 1: Start

Step 2: An array of size n is taken from the user. The number of students is also taken.

Step 3: After that, one function is called to implement a binary search.

Step 4: The function checks the minimum value in the range from zero to the sum of all elements in the array.

Step 5: We call another function to check whether the minimum value could be the answer or not.

Step 6: In this function, we check the number of students required to allocate all the books (maximum books allowed to a student should be the mid element of the range) is equal to the given student numbers or not.

Step 7: A variable is declared to store the minimum value. It updates itself when we find an appropriate value for books. After the ending of the while loop, we get the minimum value.

Step 8: The returned value will be printed.

Step 9: Stop.

Explanation of Algorithm: - In this algorithm, we use mainly two different functions. One function is used to implement binary search, and another is used to verify if the mid element is a proper value of maximum pages or not. For binary search, we use the range from the max element of the array to the sum of all elements in the array. We check the mid element by the second function. In this function, we calculate the minimum number of students required to distribute all the books among them (the condition is the maximum number of pages should not exceed the mid-value for one student). We store the mid-value in a variable and update it when the new mid-value satisfies the condition. After the ending of the loop, we get the answer.

Code: -

#include <bits/stdc++.h>
using namespace std;
 // function to check whether the minimum value could be the answer or not
bool isPossible(int array[], int n, int m, int min)
{
    int students = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (array[i] > min)
            return false;
        if (sum + array[i] > min) {
            students++;
            sum = array[i];
            if (students > m)
                return false;
        }
        else
            sum += array[i];
    }
    return true;
}
 
// function to find minimum pages using binary search
int findPages(int arr[], int n, int m)
{
    long long sum = 0;
    if (n < m)
        return -1;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    int start = 0, end = sum;
    int result = 0;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = mid;
            end = mid - 1;
        }
 
        else
            start = mid + 1;
    }
 
    return result;
}
 
// Drivers code
int main()
{
    int arr [ 50 ];
    int n ;
cin >> n;
for(int i=0 ; i<n; i++){
cin>> arr[i];
}
    int m = 2; // No. of students
 
    cout << "Minimum number of pages = "
         << findPages(arr, n, m) << endl;
    return 0;
}

Input-

[ 10, 20, 30, 40, 50 ] and 2

Output- 

Minimum number of pages = 90

Input-

[ 10, 20, 30, 40 ] and 2

Output- 

Minimum number of pages = 60

Complexity Analysis: -

Time complexity- If N is the size of the array, max is the element of the array, and M is the sum of all the elements of the array then the complexity is O(N*log (M – max)).

Space complexity- Space complexity will be O(1).