Allocate Minimum Pages Binary Search on Answer in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the search range for binary search.

DSA C++

int start = [1];
int end = 0;
for (int i = 0; i < n; i++) {
    end += arr[i];
    if (arr[i] > start) start = arr[i];
}

Drag options to blanks, or click blank then click option'

A0

Barr[0]

CINT_MAX

DINT_MIN

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing start with 0 may fail if all elements are negative.

Initializing start with arr[0] without checking all elements.

The start of the binary search range should be the maximum single element, so initializing start with INT_MIN ensures we find the maximum value in the array.

2fill in blank

medium

Complete the code to check if allocation is possible with given max pages.

DSA C++

bool isPossible(int arr[], int n, int m, int mid) {
    int studentCount = 1;
    int pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pageSum + arr[i] > [1]) {
            studentCount++;
            pageSum = arr[i];
            if (studentCount > m) return false;
        } else {
            pageSum += arr[i];
        }
    }
    return true;
}

Drag options to blanks, or click blank then click option'

Amid

Bm

Cn

DpageSum

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with m or n instead of mid.

Not resetting pageSum after allocating to a new student.

We check if adding the current book pages exceeds the mid value, which represents the maximum pages allowed per student.

3fill in blank

hard

Fix the error in the binary search loop condition.

DSA C++

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

Drag options to blanks, or click blank then click option'

A<=

B>

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= or > causes the loop to never run or run incorrectly.

Using <= can cause infinite loops.

The binary search should continue while start is less than end to avoid infinite loops and off-by-one errors.

4fill in blank

hard

Fill both blanks to complete the function that returns the minimum pages allocation.

DSA C++

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

Drag options to blanks, or click blank then click option'

AINT_MIN

B0

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for start may fail if array has negative values.

Using <= in while loop causes infinite loops.

Initialize start with INT_MIN to find max element; use '<' in while loop for correct binary search.

5fill in blank

hard

Fill all three blanks to complete the main function that reads input and prints the result.

DSA C++

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

bool isPossible(int arr[], int n, int m, int mid);
int findPages(int arr[], int n, int m);

int main() {
    int n, m;
    cin >> [1] >> [2];
    int arr[[3]];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << findPages(arr, n, m) << endl;
    return 0;
}

Drag options to blanks, or click blank then click option'

An

Bm

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping n and m in input reading.

Declaring array with wrong size.

Read n and m from input, then declare array of size n.

Practice

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

easy

A. To assign pages randomly to students

B. To maximize the total number of pages assigned

C. To find the average number of pages per student

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

Solution

1. Step 1: Understand the problem objective

   The problem wants to divide book pages among students so that the student with the most pages has as few pages as possible.

2. Step 2: Recognize the use of binary search on answer

   We use binary search on the range of possible maximum pages to find the minimum feasible maximum.

3. Final Answer:

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

4. Quick Check:

   Goal = minimize max pages per student [OK]

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

Common Mistakes:

• Thinking it maximizes total pages
• Confusing average with maximum
• Ignoring the binary search approach

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

easy

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

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

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

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

Solution

1. Step 1: Determine the minimum and maximum boundaries

   The minimum possible max pages is the largest single book (no student can get less than that), and the maximum is the sum of all pages (one student gets all books).

2. Step 2: Set binary search boundaries accordingly

   So, low = max pages in a single book, high = sum of all pages.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

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

3. What will be the output of the following C++ code snippet for the Allocate Minimum Pages problem?

int pages[] = {10, 20, 30, 40};
int n = 4, students = 2;

// Function to check feasibility
bool isPossible(int mid) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pages[i] > mid) return false;
        if (pageSum + pages[i] > mid) {
            studentCount++;
            pageSum = pages[i];
            if (studentCount > students) return false;
        } else {
            pageSum += pages[i];
        }
    }
    return true;
}

int low = 40, high = 100, result = high;
while (low <= high) {
    int mid = (low + high) / 2;
    if (isPossible(mid)) {
        result = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}
std::cout << result << std::endl;

medium

A. 50

B. 70

C. 60

D. 40

Solution

1. Step 1: Understand the feasibility check

   The function checks if pages can be allocated so no student gets more than mid pages.

2. Step 2: Binary search to find minimum max pages

   Try mid values between 40 and 100. The minimum feasible max pages is 60 (assign {10,20,30} to student 1 and {40} to student 2).

3. Final Answer:

   60 -> Option C

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Check feasibility by simulating allocation [OK]

Common Mistakes:

• Not updating student count correctly
• Choosing mid incorrectly
• Ignoring single book page size

4. Identify the bug in the following C++ code snippet for the Allocate Minimum Pages problem:

bool isPossible(int mid, int pages[], int n, int students) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pageSum + pages[i] <= mid) {
            pageSum += pages[i];
        } else {
            studentCount++;
            pageSum = pages[i];
        }
    }
    return studentCount <= students;
}

medium

A. Missing check if a single book has pages more than mid

B. Incorrect increment of studentCount

C. Page sum should reset to zero instead of pages[i]

D. Loop should run from i = 1 instead of 0

Solution

1. Step 1: Analyze the feasibility function

   The function tries to allocate books without exceeding mid pages per student.

2. Step 2: Identify missing validation

   It does not check if any single book has pages more than mid, which makes allocation impossible.

3. Final Answer:

   Missing check if a single book has pages more than mid -> Option A

4. Quick Check:

   Check single book pages <= mid [OK]

Hint: Always check single book pages against mid [OK]

Common Mistakes:

• Ignoring single book size check
• Resetting pageSum incorrectly
• Wrong loop start index

5. Given the books with pages {12, 34, 67, 90} and 2 students, what is the minimum maximum number of pages a student can get when using binary search on answer to allocate books optimally?

hard

A. 90

B. 113

C. 101

D. 67

Solution

1. Step 1: Set binary search boundaries

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

2. Step 2: Use binary search to find minimum max pages

   Check mid values. The minimum feasible max pages is 113 (assign {12,34,67}=113 to one student and {90} to the other).

3. Final Answer:

   113 -> Option B

4. Quick Check:

   Minimum max pages = 113 [OK]

Hint: Binary search between max single book and total pages [OK]

Common Mistakes:

• Choosing max single book as answer
• Choosing sum of pages as answer
• Not testing feasibility properly