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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation for Given Books and Students

Given the array of book pages and number of students, what is the minimum maximum number of pages allocated to a student?

DSA C++

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

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

#include <iostream>
int main() {
    int arr[] = {12, 34, 67, 90};
    int n = 4;
    int m = 2;
    std::cout << findPages(arr, n, m) << std::endl;
    return 0;
}

A 113

B 157

C 90

D 67

💡 Hint

Think about dividing books so that the maximum pages assigned to any student is minimized.

The minimum maximum pages allocated to a student is 113. The allocation can be [12, 34, 67] and [90], where the max pages is 113.

❓ Predict Output

intermediate

Output for Single Student Allocation

What is the output when there is only one student for the given books?

DSA C++

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

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

#include <iostream>
int main() {
    int arr[] = {10, 20, 30, 40};
    int n = 4;
    int m = 1;
    std::cout << findPages(arr, n, m) << std::endl;
    return 0;
}

A 40

B 30

C 10

D 100

💡 Hint

If only one student is there, he must read all books.

With one student, all books must be allocated to that student, so the sum of all pages is the answer.

🔧 Debug

advanced

Identify the Error in Allocation Check Function

What error will this code produce when checking if allocation is possible?

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 (arr[i] >= mid) return false;
        if (pageSum + arr[i] > mid) {
            studentCount++;
            pageSum = arr[i];
            if (studentCount > m) return false;
        } else {
            pageSum += arr[i];
        }
    }
    return true;
}

A Returns false incorrectly when arr[i] == mid

B Returns true incorrectly when arr[i] > mid

C Causes runtime error due to uninitialized variable

D No error, works correctly

💡 Hint

Check the condition that compares arr[i] and mid carefully.

The condition 'arr[i] >= mid' returns false even when arr[i] equals mid, which should be allowed. It should be 'arr[i] > mid'.

🧠 Conceptual

advanced

Why Use Binary Search in Allocate Minimum Pages Problem?

Why is binary search used on the answer space instead of the input array in the Allocate Minimum Pages problem?

A Because the input array is unsorted and cannot be searched directly

B Because binary search is faster on arrays than on numbers

C Because the answer lies between the max single book pages and sum of all pages, which forms a sorted search space

D Because binary search can only be applied to the input array

💡 Hint

Think about the range of possible answers and how binary search helps narrow it down.

The minimum maximum pages must be at least the largest single book and at most the sum of all pages. This range is sorted and binary search efficiently finds the minimum feasible value.

❓ Predict Output

expert

Output for Complex Allocation Scenario

What is the output of the minimum maximum pages allocated for the following input?

DSA C++

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

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

#include <iostream>
int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = 8;
    int m = 3;
    std::cout << findPages(arr, n, m) << std::endl;
    return 0;
}

A 210

B 150

C 170

D 120

💡 Hint

Try to split books into 3 students so that the maximum pages assigned is minimized.

The allocation can be [10,20,30,40,50], [60,70], [80] with max pages 150, which is the minimum possible.