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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation Function

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

DSA C#

using System;

class Program {
    static 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;
    }

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

    static void Main() {
        int[] pages = {12, 34, 67, 90};
        int students = 2;
        Console.WriteLine(AllocateMinimumPages(pages, pages.Length, students));
    }
}

A 157

B 113

C 90

D 67

💡 Hint

Think about how binary search narrows down the maximum pages allocated to a student.

The function tries to minimize the maximum number of pages assigned to a student. The minimum feasible maximum is 113 for the given input.

🧠 Conceptual

intermediate

Understanding the Role of 'IsPossible' Function

In the Allocate Minimum Pages problem, what is the main purpose of the 'IsPossible' function?

A To check if the current mid value can be used to allocate pages without exceeding the number of students

B To calculate the total number of pages in the array

C To sort the array of pages before allocation

D To find the maximum number of pages in the array

💡 Hint

Consider what the function returns true or false for.

'IsPossible' checks if it is feasible to allocate pages such that no student gets more than 'mid' pages and all students are assigned.

🔧 Debug

advanced

Identify the Bug in Allocation Code

What error will occur when running this code snippet for Allocate Minimum Pages problem?

DSA C#

static 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 No error, runs correctly

B StackOverflowException

C NullReferenceException

D IndexOutOfRangeException

💡 Hint

Check the loop boundary condition carefully.

The loop runs from i = 0 to i <= n, which causes an index out of range when i equals n.

🚀 Application

advanced

Minimum Pages Allocation for Custom Input

Given the array of pages [10, 20, 30, 40, 50] and 3 students, what is the minimum maximum number of pages allocated to a student?

A 60

B 70

C 90

D 50

💡 Hint

Try to split the array into 3 parts minimizing the maximum sum.

The optimal allocation is [10,20,30], [40], [50] with maximum pages 60.

❓ Predict Output

expert

Output of Modified Allocation with Single Student

What will be the output of the AllocateMinimumPages function when given pages = [5, 10, 15, 20] and students = 1?

DSA C#

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

static 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;
}

static void Main() {
    int[] pages = {5, 10, 15, 20};
    int students = 1;
    Console.WriteLine(AllocateMinimumPages(pages, pages.Length, students));
}

A 15

B 20

C 50

D 5

💡 Hint

With only one student, all pages must be allocated to that student.

Since there is only one student, the maximum pages allocated is the sum of all pages: 5+10+15+20=50.

Practice

1. What is the main goal of the Allocate Minimum Pages problem when using binary search on the 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 to students

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Identify the binary search target

   Binary search is used to find the minimum possible maximum pages assigned to any 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 any student gets [OK]

Common Mistakes:

• Thinking it maximizes total pages
• Confusing average with maximum
• Assuming random assignment

2. Which of the following is the correct way to initialize the binary search range for the minimum pages problem in C#?

easy

A. int low = 0, high = pages.Max();

B. int low = 0, high = pages.Sum();

C. int low = pages.Max(), high = pages.Sum();

D. int low = pages.Sum(), high = pages.Max();

Solution

1. Step 1: Determine the minimum and maximum possible pages

   The minimum max pages must be at least the largest single book (pages.Max()), and the maximum is the sum of all pages (pages.Sum()).

2. Step 2: Set binary search range accordingly

   Set low = pages.Max() and high = pages.Sum() to cover all possible max page values.

3. Final Answer:

   int low = pages.Max(), high = pages.Sum(); -> Option C

4. Quick Check:

   low = max page, high = sum pages [OK]

Hint: Low starts at max single book, high at total pages [OK]

Common Mistakes:

• Starting low at 0 (too low)
• Swapping low and high
• Using max as low and max as high

3. Given the array pages = [10, 20, 30, 40] and students = 2, what is the minimum maximum pages assigned after running the binary search solution?

medium

A. 70

B. 50

C. 40

D. 60

Solution

1. Step 1: Understand the problem with given input

   We want to split [10,20,30,40] into 2 students minimizing the max pages assigned.

2. Step 2: Check possible splits and their max pages

   Possible splits: [10,20,30] & [40] max=60; [10,20] & [30,40] max=70; [10] & [20,30,40] max=90; [10,20,30,40] & [] invalid. The minimum max is 60 or 50? Actually, [10,20,30] & [40] max=60, but [10,20] & [30,40] max=70. Check if 50 is possible: [10,20] & [30,40] max=70 >50 no; [10,20,30] & [40] max=60 >50 no; So 50 is not possible. But 60 is possible. So minimum max pages is 60.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try splitting pages to minimize largest sum per student [OK]

Common Mistakes:

• Choosing max single book (40) as answer
• Choosing total sum (100) as answer
• Not checking all splits

4. Consider this C# code snippet for checking feasibility in the minimum pages problem:

bool IsPossible(int[] pages, int students, int mid) {
    int count = 1, sum = 0;
    foreach (int page in pages) {
        if (sum + page > mid) {
            count++;
            sum = page;
        } else {
            sum += page;
        }
    }
    return count <= students;
}

What is the bug in this code?

medium

A. It should return count >= students instead of count <= students

B. It does not handle the case when a single book has more pages than mid

C. It increments count incorrectly inside the loop

D. It resets sum to zero instead of page after incrementing count

Solution

1. Step 1: Analyze the feasibility check logic

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

2. Step 2: Identify missing check for single book pages

   If any single book has pages > mid, allocation is impossible, but code does not check this, causing wrong results.

3. Final Answer:

   It does not handle the case when a single book has more pages than mid -> Option B

4. Quick Check:

   Check single book > mid to avoid wrong feasibility [OK]

Hint: Always check if any single book exceeds mid [OK]

Common Mistakes:

• Ignoring single book size check
• Wrong comparison operator in return
• Resetting sum incorrectly

5. You have pages = [12, 34, 67, 90] and students = 2. Using binary search on answer, what is the minimum maximum pages that can be allocated? Also, explain why the answer is not the maximum single book pages.

hard

A. 113, because splitting as [12,34,67] and [90] minimizes max pages

B. 90, because the largest single book sets the minimum max pages

C. 67, because the average pages per student is less than 70

D. 123, because total pages must be divided equally

Solution

1. Step 1: Calculate total and max pages

   Total pages = 12+34+67+90 = 203; max single book = 90.

2. Step 2: Check possible splits for 2 students

   Splits: [12,34,67] & [90] max=113; [12,34] & [67,90] max=157; [12] & [34,67,90] max=191. Minimum max pages is 113.

3. Step 3: Explain why answer is not max single book

   Because 90 alone is too small to cover all pages in 2 students without exceeding max pages, the minimum max pages must be higher than 90.

4. Final Answer:

   113, because splitting as [12,34,67] and [90] minimizes max pages -> Option A

5. Quick Check:

   Minimum max pages = 113 > max single book 90 [OK]

Hint: Check splits; answer ≥ max single book, often higher [OK]

Common Mistakes:

• Choosing max single book as answer
• Ignoring total pages sum
• Assuming equal division always works