Allocate Minimum Pages Binary Search on Answer in DSA C++ - Build from Scratch

Allocate Minimum Pages using Binary Search on Answer

📖 Scenario: You are a librarian who needs to allocate books to students. Each book has a certain number of pages. You want to distribute the books so that the student who gets the most pages has as few pages as possible. Books must be allocated in order and each student must get at least one book.

🎯 Goal: Build a program that finds the minimum possible maximum number of pages assigned to a student using binary search on the answer.

📋 What You'll Learn

Create a vector called books with these exact page counts: 12, 34, 67, 90

Create an integer variable called students and set it to 2

Write a function called isPossible that takes books, students, and a maxPages integer, and returns true if allocation is possible without exceeding maxPages per student

Use binary search between the maximum single book pages and the sum of all pages to find the minimum maximum pages

Print the minimum maximum pages after allocation

💡 Why This Matters

🌍 Real World

This problem models distributing workloads or resources evenly, such as assigning books to students or tasks to workers.

💼 Career

Understanding binary search on answer is useful in software engineering roles that require optimization and efficient resource allocation.

1

Create the books vector

Create a vector of integers called books with these exact values: 12, 34, 67, 90

DSA C++

# Create the vector books with the given page counts
# Your code here

Hint

Use std::vector<int> and initialize it with the given numbers inside curly braces.

2

Add the students variable

Add an integer variable called students and set it to 2 below the books vector

DSA C++

#include 
#include 

int main() {
    std::vector books = {12, 34, 67, 90};
    // Declare students variable
    // Your code here
    return 0;
}

Hint

Declare int students = 2; after the books vector.

3

Write the isPossible function

Write a function called isPossible that takes const std::vector<int>& books, int students, and int maxPages as parameters and returns true if it is possible to allocate books to students so that no student reads more than maxPages pages. Books must be allocated in order and each student must get at least one book.

DSA C++

#include 
#include 

bool isPossible(const std::vector& books, int students, int maxPages) {
    // Your code here
}

int main() {
    std::vector books = {12, 34, 67, 90};
    int students = 2;
    return 0;
}

Hint

Use a loop to sum pages and count students needed. Return false if any book has more pages than maxPages or if students needed exceed given students.

4

Find and print the minimum maximum pages

Use binary search between the maximum pages in books and the sum of all pages in books to find the minimum maximum pages that can be allocated to students. Print the result using std::cout.

DSA C++

#include 
#include 

int main() {
    std::vector books = {12, 34, 67, 90};
    int students = 2;
    // Use binary search to find minimum max pages
    // Your code here
    return 0;
}

Hint

Calculate the max single book pages and total pages. Use binary search between these to find minimum max pages. Print the final answer.