Allocate Minimum Number of Pages

You are given a list of N books where each book has a certain number of pages, and you have to allocate these books to M students.

Your goal is to distribute the books among students in such a way that:

• Each student gets at least one book.
• Each book is allocated to exactly one student.
• Books allocated to a student must be in a contiguous block (i.e., no skipping).

The task is to minimize the maximum number of pages assigned to a student across all students.

If it is not possible to allocate the books as per the rules, return -1.

Understanding the Problem

We are given an array where each element represents the number of pages in a book. Our goal is to assign these books to a given number of students such that:

• Each student gets at least one book.
• Books are assigned in contiguous blocks (no skipping allowed).
• We minimize the maximum number of pages assigned to any student.

This is a classic allocation problem where we want to fairly distribute the load. The fairness is measured by how low we can keep the highest page count that any single student gets.

Step-by-Step Solution with Example

Step 1: Understand the Inputs and Outputs

Suppose we have the books [12, 34, 67, 90] and we want to assign them to 2 students.

Each student must receive a continuous block of books. We must split this array into two parts such that the student who reads the most pages still reads as little as possible.

Step 2: Identify the Search Range

We use binary search between:

• low = max(arr) → No student can get less than the largest book.
• high = sum(arr) → One student takes all books.

For our example, low = 90, high = 203.

Step 3: Apply Binary Search to Minimize the Maximum Pages

We try to find the minimum value of the maximum pages a student reads. At each step, we pick mid = (low + high) // 2 and check:

Can we divide books into ≤ k students so that no one gets more than mid pages?

If yes, we try to find a smaller value. If not, we search higher.

Step 4: Write a Helper Function to Check Feasibility

We count how many students are needed if each student is allowed a maximum of mid pages. We go through the books, summing their pages until we exceed mid, then assign to a new student.

Step 5: Apply the Logic with Our Example

Try mid = 120. Can we divide books so no student gets more than 120 pages?

• Student 1 → 12 + 34 + 67 = 113 (OK)
• Student 2 → 90 (OK)

This is valid. Try smaller value to minimize max pages.

Step 6: Find the Minimum Possible Maximum

Keep repeating until low > high. The lowest mid for which allocation is possible is the answer.

In this example, the answer would be 113 — that’s the least maximum load possible.

Edge Cases

• Empty book list — Nothing to assign → return -1.
• Zero students — No one to assign → return -1.
• More students than books — Not possible to assign at least one book per student → return -1.
• One student — Must read all books → return sum(arr).
• Equal books and students — Each gets one → return max(arr).

Finally

This problem is best solved using binary search on the answer range. By narrowing down the maximum number of pages a student can take, and validating it efficiently, we avoid brute force.

Always remember to handle edge cases up front, and make sure your solution respects the constraints: contiguous blocks and at least one book per student.

This is a perfect example of optimization under constraints — a very common pattern in algorithm design!

1. Set low = max(arr) and high = sum(arr).
2. While low ≤ high, do:
3. → Calculate mid = (low + high) / 2.
4. → Check if it's possible to allocate books so that no student has more than mid pages using a helper function.
5. → If possible, store the result and try to reduce it: high = mid - 1.
6. → If not possible, increase the range: low = mid + 1.
7. Return the minimum value found that satisfies the condition.

#include <stdio.h>

int isPossible(int arr[], int n, int m, int maxPages) {
    int students = 1, pages = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxPages) return 0;
        if (pages + arr[i] > maxPages) {
            students++;
            pages = arr[i];
        } else {
            pages += arr[i];
        }
    }
    return students <= m;
}

int findMinimumPages(int arr[], int n, int m) {
    if (m > n) return -1;
    int low = arr[0], high = 0, result = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] > low) low = arr[i];
        high += arr[i];
    }
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int arr[] = {12, 34, 67, 90};
    int students = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Minimum Maximum Pages: %d\n", findMinimumPages(arr, n, students));
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

bool isPossible(int arr[], int n, int m, int maxPages) {
    int students = 1, pages = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxPages) return false;
        if (pages + arr[i] > maxPages) {
            students++;
            pages = arr[i];
        } else {
            pages += arr[i];
        }
    }
    return students <= m;
}

int findMinimumPages(int arr[], int n, int m) {
    if (m > n) return -1;
    int low = *max_element(arr, arr + n);
    int high = 0, result = -1;
    for (int i = 0; i < n; i++) high += arr[i];
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int arr[] = {12, 34, 67, 90};
    int students = 2;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum Maximum Pages: " << findMinimumPages(arr, n, students) << endl;
    return 0;
}

def is_possible(arr, m, max_pages):
    students = 1
    pages = 0
    for book in arr:
        if book > max_pages:
            return False
        if pages + book > max_pages:
            students += 1
            pages = book
        else:
            pages += book
    return students <= m

def find_minimum_pages(arr, m):
    if m > len(arr):
        return -1
    low = max(arr)
    high = sum(arr)
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if is_possible(arr, m, mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1
    return result

arr = [12, 34, 67, 90]
students = 2
print("Minimum Maximum Pages:", find_minimum_pages(arr, students))

public class BookAllocator {
  public static boolean isPossible(int[] arr, int m, int maxPages) {
    int students = 1;
    int pages = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] > maxPages) return false;
      if (pages + arr[i] > maxPages) {
        students++;
        pages = arr[i];
      } else {
        pages += arr[i];
      }
    }
    return students <= m;
  }

  public static int findMinimumPages(int[] arr, int m) {
    if (m > arr.length) return -1;
    int low = arr[0], high = 0;
    for (int pages : arr) {
      low = Math.max(low, pages);
      high += pages;
    }

    int result = -1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (isPossible(arr, m, mid)) {
        result = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return result;
  }

  public static void main(String[] args) {
    int[] arr = {12, 34, 67, 90};
    int students = 2;
    int minPages = findMinimumPages(arr, students);
    System.out.println("Minimum Maximum Pages: " + minPages);
  }
}

function isPossible(arr, m, maxPages) {
  let students = 1;
  let pages = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > maxPages) return false;
    if (pages + arr[i] > maxPages) {
      students++;
      pages = arr[i];
    } else {
      pages += arr[i];
    }
  }
  return students <= m;
}

function findMinimumPages(arr, m) {
  if (m > arr.length) return -1;
  let low = Math.max(...arr);
  let high = arr.reduce((a, b) => a + b, 0);
  let result = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(arr, m, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

let arr = [12, 34, 67, 90];
let students = 2;
console.log("Minimum Maximum Pages:", findMinimumPages(arr, students));

package main

import (
    "fmt"
)

func isPossible(arr []int, m int, maxPages int) bool {
    students := 1
    pages := 0
    for _, book := range arr {
        if book > maxPages {
            return false
        }
        if pages+book > maxPages {
            students++
            pages = book
        } else {
            pages += book
        }
    }
    return students <= m
}

func findMinimumPages(arr []int, m int) int {
    if m > len(arr) {
        return -1
    }
    low, high := arr[0], 0
    for _, pages := range arr {
        if pages > low {
            low = pages
        }
        high += pages
    }
    result := -1
    for low <= high {
        mid := low + (high-low)/2
        if isPossible(arr, m, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

func main() {
    arr := []int{12, 34, 67, 90}
    students := 2
    fmt.Println("Minimum Maximum Pages:", findMinimumPages(arr, students))
}

fn is_possible(arr: &Vec<i32>, m: i32, max_pages: i32) -> bool {
    let mut students = 1;
    let mut pages = 0;
    for &book in arr.iter() {
        if book > max_pages {
            return false;
        }
        if pages + book > max_pages {
            students += 1;
            pages = book;
        } else {
            pages += book;
        }
    }
    students <= m
}

fn find_minimum_pages(arr: Vec<i32>, m: i32) -> i32 {
    if m as usize > arr.len() {
        return -1;
    }
    let mut low = *arr.iter().max().unwrap();
    let mut high: i32 = arr.iter().sum();
    let mut result = -1;
    while low <= high {
        let mid = low + (high - low) / 2;
        if is_possible(&arr, m, mid) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    result
}

fn main() {
    let arr = vec![12, 34, 67, 90];
    let students = 2;
    println!("Minimum Maximum Pages: {}", find_minimum_pages(arr, students));
}

fun isPossible(arr: IntArray, m: Int, maxPages: Int): Boolean {
    var students = 1
    var pages = 0
    for (book in arr) {
        if (book > maxPages) return false
        if (pages + book > maxPages) {
            students++
            pages = book
        } else {
            pages += book
        }
    }
    return students <= m
}

fun findMinimumPages(arr: IntArray, m: Int): Int {
    if (m > arr.size) return -1
    var low = arr.maxOrNull() ?: 0
    var high = arr.sum()
    var result = -1
    while (low <= high) {
        val mid = low + (high - low) / 2
        if (isPossible(arr, m, mid)) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

fun main() {
    val arr = intArrayOf(12, 34, 67, 90)
    val students = 2
    println("Minimum Maximum Pages: ${findMinimumPages(arr, students)}")
}

func isPossible(_ arr: [Int], _ m: Int, _ maxPages: Int) -> Bool {
    var students = 1
    var pages = 0
    for book in arr {
        if book > maxPages {
            return false
        }
        if pages + book > maxPages {
            students += 1
            pages = book
        } else {
            pages += book
        }
    }
    return students <= m
}

func findMinimumPages(_ arr: [Int], _ m: Int) -> Int {
    if m > arr.count { return -1 }
    var low = arr.max() ?? 0
    var high = arr.reduce(0, +)
    var result = -1
    while low <= high {
        let mid = low + (high - low) / 2
        if isPossible(arr, m, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

let arr = [12, 34, 67, 90]
let students = 2
print("Minimum Maximum Pages: \(findMinimumPages(arr, students))")

function isPossible(arr: number[], m: number, maxPages: number): boolean {
  let students = 1;
  let pages = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > maxPages) return false;
    if (pages + arr[i] > maxPages) {
      students++;
      pages = arr[i];
    } else {
      pages += arr[i];
    }
  }
  return students <= m;
}

function findMinimumPages(arr: number[], m: number): number {
  if (m > arr.length) return -1;
  let low = Math.max(...arr);
  let high = arr.reduce((a, b) => a + b, 0);
  let result = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(arr, m, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

const arr = [12, 34, 67, 90];
const students = 2;
console.log("Minimum Maximum Pages:", findMinimumPages(arr, students));

Time complexity

Space complexity

O(1)

Only a fixed number of variables are used. No extra space is needed.