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.