Allocate Minimum Pages Binary Search on Answer in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation for Given Books and Students

What is the output of the following Java code that uses binary search to allocate minimum pages to students?

DSA Java

public class Solution {
    public static boolean isPossible(int[] books, int students, int maxPages) {
        int count = 1, sum = 0;
        for (int pages : books) {
            if (pages > maxPages) return false;
            if (sum + pages > maxPages) {
                count++;
                sum = pages;
                if (count > students) return false;
            } else {
                sum += pages;
            }
        }
        return true;
    }

    public static int findPages(int[] books, int students) {
        int start = 0, end = 0;
        for (int pages : books) end += pages;
        int result = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (isPossible(books, students, mid)) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] books = {12, 34, 67, 90};
        int students = 2;
        System.out.println(findPages(books, students));
    }
}

A 67

B 157

C 90

D 113

💡 Hint

Think about how binary search narrows down the maximum pages per student.

The minimum maximum pages allocated to 2 students for books {12,34,67,90} is 113. The allocation can be (12,34,67) and (90), where the max pages is 113.

❓ Predict Output

intermediate

Result of Allocation Check Function

What does the isPossible function return for books = {10, 20, 30, 40} with students = 2 and maxPages = 50?

DSA Java

public static boolean isPossible(int[] books, int students, int maxPages) {
    int count = 1, sum = 0;
    for (int pages : books) {
        if (pages > maxPages) return false;
        if (sum + pages > maxPages) {
            count++;
            sum = pages;
            if (count > students) return false;
        } else {
            sum += pages;
        }
    }
    return true;
}

// Call: isPossible(new int[]{10,20,30,40}, 2, 50)

A true

B false

C SyntaxError

D RuntimeException

💡 Hint

Check if books can be divided into 2 students without exceeding 50 pages each.

The books can be allocated as (10,20,30) and (40). The first student gets 60 pages which is more than 50, so allocation fails. But wait, sum + pages > maxPages triggers new student allocation. Actually, allocation is (10,20) and (30,40) with max 50 pages each, so returns true.

🔧 Debug

advanced

Identify the Error in Binary Search Allocation Code

What error will occur when running this code snippet for allocating minimum pages?

DSA Java

public static int findPages(int[] books, int students) {
    int start = 0, end = 0;
    for (int pages : books) end += pages;
    int result = -1;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (isPossible(books, students, mid)) {
            result = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return result;
}

A Returns -1 always

B Correct output

C Infinite loop

D ArrayIndexOutOfBoundsException

💡 Hint

Check the binary search loop condition and how start and end are updated.

The loop condition 'while (start < end)' with 'end = mid - 1' can cause start to never reach end if mid equals start, causing infinite loop.

❓ Predict Output

advanced

Output of Allocation with Large Book Pages

What is the output of the minimum pages allocation for books = {100, 200, 300, 400, 500} and students = 3?

DSA Java

public static void main(String[] args) {
    int[] books = {100, 200, 300, 400, 500};
    int students = 3;
    System.out.println(findPages(books, students));
}

// Uses previously defined findPages and isPossible methods

A 500

B 700

C 900

D 600

💡 Hint

Try to split books into 3 students minimizing the maximum pages.

The allocation can be (100,200,300), (400), (500) with max pages 700, which is minimum possible.

🧠 Conceptual

expert

Why Binary Search is Used in Allocate Minimum Pages Problem?

Which reason best explains why binary search is used to solve the Allocate Minimum Pages problem?

A Because the answer lies within a numeric range and feasibility can be checked efficiently

B Because it sorts the books array before allocation

C Because it uses recursion to allocate pages to students

D Because it uses a hash map to store intermediate results

💡 Hint

Think about how binary search narrows down the possible maximum pages.

Binary search is used on the range of possible maximum pages. For each mid value, feasibility is checked. This reduces time complexity.

Practice

1. What is the main goal of the Allocate Minimum Pages problem using binary search on answer?

easy

A. To minimize the maximum number of pages assigned to a student

B. To maximize the total number of pages assigned

C. To find the average number of pages per student

D. To assign pages randomly among students

Solution

1. Step 1: Understand the problem objective

   The problem asks to allocate books to students so that the maximum pages assigned to any student is as small as possible.

2. Step 2: Identify the goal of binary search on answer

   Binary search is used to find the minimum possible maximum pages that can be assigned to a student.

3. Final Answer:

   To minimize the maximum number of pages assigned to a student -> Option A

4. Quick Check:

   Goal = minimize max pages [OK]

Hint: Focus on minimizing the largest pages assigned [OK]

Common Mistakes:

• Thinking the goal is to maximize pages
• Confusing average pages with maximum pages
• Assuming random allocation is acceptable

2. Which of the following is the correct way to initialize the binary search boundaries for the Allocate Minimum Pages problem in Java?

easy

A. int low = 0; int high = max pages in a single book;

B. int low = 0; int high = sum of all pages;

C. int low = max pages in a single book; int high = sum of all pages;

D. int low = sum of all pages; int high = max pages in a single book;

Solution

1. Step 1: Determine the minimum possible max pages

   The minimum max pages must be at least the largest single book's pages, because no book can be split.

2. Step 2: Determine the maximum possible max pages

   The maximum max pages is the sum of all pages if one student gets all books.

3. Final Answer:

   int low = max pages in a single book; int high = sum of all pages; -> Option C

4. Quick Check:

   low = max book pages, high = total pages [OK]

Hint: Low = max single book, High = sum all pages [OK]

Common Mistakes:

• Setting low to 0 which is invalid
• Swapping low and high values
• Using average pages as boundaries

3. Consider the books with pages [10, 20, 30, 40] and 2 students. What is the minimum maximum pages allocated to a student?

medium

A. 40

B. 70

C. 50

D. 60

Solution

1. Step 1: Check possible max pages allocations

   Try to split books so that max pages per student is minimized. Possible splits: [10,20,30] and [40] max=60; or [10,20] and [30,40] max=70.

2. Step 2: Choose minimum max pages

   Between 60 and 70, 60 is smaller and valid allocation.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splits and pick smallest max sum [OK]

Common Mistakes:

• Choosing sum of all pages as answer
• Ignoring largest single book pages
• Incorrectly splitting books

4. Given the following code snippet for checking feasibility in the Allocate Minimum Pages problem, what is the bug?

boolean isPossible(int[] pages, int students, int mid) {
    int count = 1, sum = 0;
    for (int page : pages) {
        sum += page;
        if (sum > mid) {
            count++;
            sum = 0;
        }
    }
    return count <= students;
}

medium

A. sum should be reset to current page, not zero, after count increment

B. count should be reset to zero inside the loop

C. The loop should start from index 1, not zero

D. The function should return count >= students

Solution

1. Step 1: Analyze sum reset logic

   When sum exceeds mid, count increments but sum resets to zero, losing the current page's value.

2. Step 2: Correct sum reset to current page

   Sum should reset to current page's value to include it in the new student's allocation.

3. Final Answer:

   sum should be reset to current page, not zero, after count increment -> Option A

4. Quick Check:

   Reset sum = current page [OK]

Hint: Reset sum to current page, not zero [OK]

Common Mistakes:

• Resetting sum to zero loses current page
• Returning wrong comparison for count and students
• Incorrect loop indexing

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages that can be allocated to a student? Show the reasoning.

hard

A. 90

B. 113

C. 101

D. 67

Solution

1. Step 1: Set binary search boundaries

   Low = max single book pages = 90, High = sum = 12+34+67+90=203.

2. Step 2: Check mid and feasibility

   Mid = (90+203)/2=146. Check if allocation possible with max 146 pages per student: [12,34,67] sum=113 <=146, next student gets [90]. Possible with 2 students.

3. Step 3: Narrow search

   Try lower mid: (90+146)/2=118. Check allocation: [12,34,67] sum=113 <=118, next student [90]. Possible.

4. Step 4: Try even lower mid

   Mid = (90+118)/2=104. Allocation: [12,34,67] sum=113 >104, so split: [12,34] sum=46 <=104, next student [67,90] sum=157 >104 not possible.

5. Step 5: Increase low to 105 and continue

   Mid = (105+118)/2=111. Allocation: [12,34,67] sum=113 >111 no, split: [12,34] sum=46 <=111, next student [67,90] sum=157 >111 no.

6. Step 6: Mid = (112+118)/2=115

   Allocation: [12,34,67] sum=113 <=115 yes, next student [90]. Possible.

7. Step 7: Narrow down to minimum feasible

   Try mid= (112+114)/2=113 allocation possible, mid=112 allocation not possible.

8. Final Answer:

   113 -> Option B

9. Quick Check:

   Minimum max pages = 113 [OK]

Hint: Use binary search between max book and total pages [OK]

Common Mistakes:

• Choosing max single book pages as answer
• Not checking feasibility correctly
• Stopping binary search too early