Question Name:Searching 4

Problem Description

Given number of pages in n different books and m students. The books are arranged in ascending order of number of pages.
Every student is assigned to read some consecutive books. The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.
Take Number of books, n, number of pages in n books and the number of students, m as input.
Test Case 1
Input (stdin)
4
12 34 67 90
2
Expected Output
Minimum number of pages = 113
Test Case 2
Input (stdin)
6
30 55 72 98 102 139
3
Expected Output
Minimum number of pages = 200

#include <iostream>

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

bool isPossible(int arr[], int n, int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;

// iterate over all books
for (int i = 0; i < n; i++)
{

if (arr[i] > curr_min)
return false;

if (curr_sum + arr[i] > curr_min)
{

studentsRequired++;

curr_sum = arr[i];

if (studentsRequired > m)
return false;
}

else
curr_sum += arr[i];
}
return true;
}

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 = INT_MAX;

while (start <= end)
{

int mid = (start + end) / 2;
if (isPossible(arr, n, m, mid))
{
result = min(result, mid);

end = mid - 1;
}

else

start = mid + 1;
}

return result;
}

int main()
{
int arr[10] ,i,k;
int m;
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d",&arr[i]);

}
scanf("%d",&m);
cout << "Minimum number of pages = "
<< findPages(arr, k, m) << endl;
return 0;
}

How the Code Works
1. Checking Feasibility with isPossible
The function isPossible checks if a particular maximum number of pages (curr_min) can be allocated to students without exceeding the number of students (m). It does this by:
Iterating through the books and adding up pages for the current student until adding another book would exceed curr_min.
Assigning the next student to start with the next book when this happens.
Returning false if it’s impossible to assign the books without exceeding the given maximum (curr_min).
bool isPossible(int arr[], int n, int m, int curr_min) {
    int studentsRequired = 1;
    int curr_sum = 0;

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

        if (curr_sum + arr[i] > curr_min) {
            studentsRequired++;
            curr_sum = arr[i];

            if (studentsRequired > m)
                return false;
        } else {
            curr_sum += arr[i];
        }
    }
    return true;
}

2. Finding the Minimum Pages with findPages
The findPages function uses a binary search to efficiently find the smallest possible curr_min that can be used to split the books among the students.
Binary Search: It starts with the smallest possible number of pages (start = 0) and the largest (end = sum of all pages), then narrows down until it finds the minimum possible maximum.
Calling isPossible: It calls the isPossible function with the middle value to check if it can be a valid maximum.
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 = INT_MAX;

    while (start <= end) {
        int mid = (start + end) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = min(result, mid);
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return result;
}
3. The main Function
This is where the program starts. It reads the input for the number of books, their page numbers, and the number of students. Then it calls the findPages function to get the minimum number of pages and prints it.
int main() {
    int arr[10], i, k;
    int m;
    scanf("%d", &k);
    for (i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &m);
    cout << "Minimum number of pages = " << findPages(arr, k, m) << endl;
    return 0;
}