Problem Statement
You are given an array of integers, where each integer represents the number of pages in a book. There are n books and m students. The task is to allocate books to students subject to the following conditions:
- Each student must be assigned at least one book.
- Each book can be allocated to only one student.
- The books allocated to a student must be contiguous.
Find out the maximum number of pages assigned to a student is minimum.
Examples
Example 1:
Input: pages = [12, 34, 67, 90], m = 2
Output: 113
Example 2:
Input: pages = [15, 17, 20], m = 2
Output: 32
Example 3:
Input: pages = [10, 20, 30, 40], m = 4
Output: 40
Explanation:
Each student gets exactly one book:
Student 1: {10} => 10 pages
Student 2: {20} => 20 pages
Student 3: {30} => 30 pages
Student 4: {40} => 40 pages
The maximum pages allocated is 40Example 4:
Input: pages = [10, 20, 30], m = 4
Output: -1
Explanation: Since there are more students than books, it is impossible to allocate books such that each students gets at least one book. Hence, the output is -1.Different Approaches
1️⃣ Brute Force Approach
Intuition:
The extremely naive approach is to check all possible pages from max element of the array to sum of all the elements of the array. The minimum pages for which all the books can be allocated to M students will be our answer
Approach:
- Edge case: If the number of students given is greater than the total number books, then the allocation is impossible and return -1 as answer.
- First, find the range of the search space, which will be [low, high], where low is the maximum element of the array and high is the sum of all elements of the array.
- low represents the smallest possible value for the maximum pages any student can read.
If we assign only one book to a student, the minimum pages they must read is the largest book in the array. For example:
arr = {12, 34, 67, 90}Even if we try to minimize the maximum pages, a student must read at least
90pages (the largest book). Therefore the lower bound of our search space is the maximum element of the array.
- High represents the largest possible value for the maximum pages any student can read.
- If we assign all books to one student, they would read all the pages. Thus the sum of the array (
12 + 34 + 67 + 90 = 203, in this case) represents the upper bound of the search space.
- If we assign all books to one student, they would read all the pages. Thus the sum of the array (
- low represents the smallest possible value for the maximum pages any student can read.
- Now, iterate from low to high using a for loop, inside this loop use a function to get the number of students to whom books can be allocated.
- If the value returned from the helper function is equal to the given limit(m) then return the current value of the iteration.
- Finally, if no suitable answer is found then return low(max element of the array) as an answer.
Dry Run:
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+ +-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
low = maximum of the array = 90
high = sum of all the elements of the array
= 12 + 34 + 67 + 90 = 203Iterate from low to high
low = 90
high = 203
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
^
|
i
TargetLimit = low = 90
numberOfStudents = 1
pagesForStudent = 0
Traverse through the array:
Iteration 1 (i = 0):
if(pagesForStudent + arr[i] <= TargetLimit)
0 + 12 <= 90
12 <= 90
True
set pagesForStudent = pagesForStudent + arr[i]
pagesForStudent = 0 + 12
pagesForStudent = 12
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
^
|
i
TargetLimit = low = 90
numberOfStudents = 1
pagesForStudent = 12
Traverse through the array:
Iteration 2 (i = 1):
if(pagesForStudent + arr[i] <= TargetLimit)
12 + 34 <= 90
46 <= 90
True
set pagesForStudent = pagesForStudent + arr[i]
pagesForStudent = 12 + 34
pagesForStudent = 46
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
^
|
i
TargetLimit = low = 90
numberOfStudents = 1
pagesForStudent = 46
Traverse through the array:
Iteration 3 (i = 2):
if(pagesForStudent + arr[i] <= TargetLimit)
46 + 67 <= 90
113 <= 90
False
Increment the numberOfStudents
numberOfStudents++
numberOfStudents = 2
pagesForStudent = arr[i]
pagesForStudent = arr[2]
pagesForStudent = 67 (it means this is the starting for the next student)
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
^
|
i
TargetLimit = low = 90
numberOfStudents = 2
pagesForStudent = 67
Traverse through the array:
Iteration 4 (i = 3):
if(pagesForStudent + arr[i] <= TargetLimit)
67 + 90 <= 90
157 <= 90
False
Increment the numberOfStudents
numberOfStudents++
numberOfStudents = 3
pagesForStudent = arr[i]
pagesForStudent = arr[3]
pagesForStudent = 90 (it means this is the starting for the next student)
Inner loop Termination:
+-----+-----+-----+-----+
arr = | 12 | 34 | 67 | 90 |
+-----+-----+-----+-----+
^
|
i
numberOfStudents = 3
return it to the caller
It means that if we need to maintain 90 pages
per students then we would need 3 students.Return to the caller:
We get the numberOfStudents as 3 from the callee.
Which means for the minimum of 90 pages per students,
we would need a total of 3 students however we are
given students as m = 2, which means 90 is not the
minimum of maximum pages.Next Iteration:
Continue this process for the low as 91 and high
as same 203.
Keep doing it until the callee returns the students which is equal to the given students.Code:
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
using namespace std;
// Function to calculate the number of students required to allocate books
// such that no student reads more than 'currentLimit' pages.
int countStudents(vector<int>& arr, int currentLimit) {
int possibleStudents = 1; // Start with one student
int currentSum = 0; // Track the sum of pages allocated to the current student
for (int i = 0; i < arr.size(); i++) {
// If adding the current book doesn't exceed the limit, add it
if (currentSum + arr[i] <= currentLimit) {
currentSum += arr[i];
} else {
// Otherwise, assign the current book to the next student
currentSum = arr[i];
possibleStudents++;
}
}
return possibleStudents; // Return the total number of students required
}
// Function to find the minimum of the maximum pages assigned to any student
int allocatePages(vector<int>& arr, int numberOfStudents) {
// If the number of students is greater than the number of books, allocation is impossible
if (numberOfStudents > arr.size()) {
return -1;
}
// Find the maximum number of pages in a single book (minimum possible limit)
// and the total sum of all pages (maximum possible limit)
int maxi = INT_MIN; // Initialize to the smallest possible value
int sum = 0; // Initialize the total sum of pages
for (int i = 0; i < arr.size(); i++) {
sum += arr[i]; // Calculate the total sum of pages
maxi = max(maxi, arr[i]); // Track the largest book
}
// Set the range for the possible maximum pages
int low = maxi; // Minimum possible maximum pages (largest single book)
int high = sum; // Maximum possible maximum pages (all books combined)
// Use a linear search to find the minimum maximum pages
for (; low <= high; low++) {
// Check if the current limit 'low' allows exactly 'numberOfStudents' allocations
if (countStudents(arr, low) == numberOfStudents) {
return low; // Return the smallest valid maximum pages
}
}
}
// Main function to test the allocatePages function
int main() {
vector<int> arr = {12, 34, 67, 90}; // Array of book pages
int m = 2; // Number of students
// Call the function to calculate the minimum of maximum pages
int minimumOfMaximum = allocatePages(arr, m);
// Output the result
cout << "The answer is: " << minimumOfMaximum << "\n";
return 0;
}Complexity Analysis:
- Time Complexity:
O(N * (sum - max)), whereNis the size of the array,sumis the sum of all array elements,maxis the maximum of all array elements.- The outer loop runs from
maxtosumto check all possible numbers of pages. - The inner loop, iterates over the array, thus it runs for
Ntimes.
- The outer loop runs from
- Space Complexity:
O(1)
2️⃣ Binary Search
Intuition:
Here, the idea is to use binary search algorithm to optimize the brute-force solution which was using linear search algorithm. The answer space, represented as [max element, sum of all elements], is actually sorted so, binary search algorithm can be applied here. Based on certain conditions, the search space can be divided into halves in each iteration thus enhancing the overall time complexity.
Approach:
- Edge case: If the number of students given is greater than the total number books, then the allocation is impossible and return -1 as answer.
- Take two pointers, low and high. Initialize low to max(maximum element of the array) and high to sum(sum of all the elements of the array). The range from [low,high] will define the search space.
- Now, initialize a while loop, which runs till low is less than or equal to high. Inside this loop calculate the 'mid' by using mid = (low+high) // 2 ( ‘//’ refers to integer division). The mid will be the defining the minimum possible maximum pages that can be allocated to any student.
- Calculate students by using the countStudents function, which determines how many students are needed if each student can read up to 'mid' pages.
If students is greater than m, it means mid is too small (more students are needed), so adjust low to mid + 1, else, mid might be a valid solution or could potentially be reduced, so adjust high to mid - 1. - After the binary search concludes (low > high), low will represent the minimum possible maximum pages that can be allocated to any student while ensuring m or fewer students are needed. Return low as the result.
- Working of countStudents(nums, pages):
- Start by getting the size of the array nums and store in in 'n'. Initialize students to 1, assuming at least one student is required and also initialize pagesStudent to 0, which will keep track of the total number of pages assigned to the current student.
- Iterate through the array and check if adding current element to pagesStudent will keep the total pages assigned to the current student within the limit specified by pages. If true, add the current element to pagesStudent, indicating that the current student can handle these additional pages.
- If adding the current element would exceed the limit pages, it indicates that a new student is needed to handle these pages. Increment the students counter to account for the new student. Reset pagesStudent to the current element, starting a new student with the current element's pages. Finally, return the 'student' variable.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to count the number of
students required given the maximum
pages each student can read */
int countStudents(vector<int>& nums, int pages) {
// Size of array
int n = nums.size();
int students = 1;
int pagesStudent = 0;
for (int i = 0; i < n; i++) {
if (pagesStudent + nums[i] <= pages) {
// Add pages to current student
pagesStudent += nums[i];
} else {
// Add pages to next student
students++;
pagesStudent = nums[i];
}
}
return students;
}
public:
/*Function to allocate the book to ‘m’
students such that the maximum number
of pages assigned to a student is minimum */
int findPages(vector<int>& nums, int m) {
int n = nums.size();
// Book allocation impossible
if (m > n) return -1;
// Calculate the range for binary search
int low = *max_element(nums.begin(), nums.end());
int high = accumulate(nums.begin(), nums.end(), 0);
// Binary search for minimum maximum pages
while (low <= high) {
int mid = (low + high) / 2;
int students = countStudents(nums, mid);
if (students > m) {
// go right
low = mid + 1;
}
else {
// go left
high = mid - 1;
}
}
return low;
}
};
int main() {
vector<int> arr = {25, 46, 28, 49, 24};
int n = 5;
int m = 4;
// Create an instance of the Solution class
Solution sol;
int ans = sol.findPages(arr, m);
// Output the result
cout << "The answer is: " << ans << "\n";
return 0;
}OR:
class Solution {
public:
// Function to calculate the number of students required to allocate books
// such that no student reads more than 'currentLimit' pages.
int countStudents(vector<int>& arr, int currentLimit) {
int possibleStudents = 1; // Start with one student
int currentSum = 0; // Track the sum of pages allocated to the current student
for (int i = 0; i < arr.size(); i++) {
// If adding the current book doesn't exceed the limit, add it
if (currentSum + arr[i] <= currentLimit) {
currentSum += arr[i];
} else {
// Otherwise, assign the current book to the next student
currentSum = arr[i];
possibleStudents++;
}
}
return possibleStudents; // Return the total number of students required
}
// Function to find the minimum of the maximum pages assigned to any student
int findPages(vector<int> &arr, int numberOfStudents) {
if (numberOfStudents > arr.size()) {
return -1; // Allocation impossible
}
// Determine the range for binary search
int maxi = *max_element(arr.begin(), arr.end()); // Largest single book
int sum = accumulate(arr.begin(), arr.end(), 0); // Total pages in all books
int low = maxi; // Minimum possible maximum pages
int high = sum; // Maximum possible maximum pages
int result = -1; // Store the result
while (low <= high) {
int mid = low + (high - low) / 2; // Middle point of the range
// Determine the number of students needed for this mid value
int students = countStudents(arr, mid);
if (students <= numberOfStudents) {
// If the current mid works, it's a potential answer
result = mid;
high = mid - 1; // Try for a smaller maximum
} else {
// If more students are needed, increase the limit
low = mid + 1;
}
}
return result; // Return the minimum maximum pages
}
};
Complexity Analysis:
- Time Complexity:
O(N * log(sum - max)), whereNis the size of the array,sumis the sum of all array elements,maxis the maximum of all array.- As Binary search is applied on
[max, sum].- The outer loop will run for the value of
mid. - The inner loop will runs for
Ntimes.
- The outer loop will run for the value of
- As Binary search is applied on
- Space Complexity:
O(1)