Allocate Minimum Pages Binary Search on Answer in DSA Go - 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 Go code that uses binary search to allocate minimum pages to 2 students for 4 books?

DSA Go

package main
import "fmt"
func isPossible(books []int, students int, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages > mid {
            return false
        }
        if sum+pages > mid {
            count++
            sum = pages
            if count > students {
                return false
            }
        } else {
            sum += pages
        }
    }
    return true
}
func allocateMinimumPages(books []int, students int) int {
    start, end := 0, 0
    for _, pages := range books {
        if pages > start {
            start = pages
        }
        end += pages
    }
    result := end
    for start <= end {
        mid := (start + end) / 2
        if isPossible(books, students, mid) {
            result = mid
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return result
}
func main() {
    books := []int{10, 20, 30, 40}
    students := 2
    fmt.Println(allocateMinimumPages(books, students))
}

A 70

B 50

C 60

D 40

💡 Hint

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

The minimum maximum pages allocated to 2 students for books with pages [10,20,30,40] is 60. The optimal division is [10,20,30] totaling 60 and [40] totaling 40.

🧠 Conceptual

intermediate

Understanding the Role of Binary Search in Minimum Pages Allocation

Why do we use binary search on the answer space instead of the input array when solving the Allocate Minimum Pages problem?

A Because the answer lies between the maximum single book pages and the sum of all pages, which forms a sorted range to binary search.

B Because binary search is faster on arrays than on numbers.

C Because the books array is always sorted, so binary search applies directly on it.

D Because binary search helps to sort the books before allocation.

💡 Hint

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

The problem's answer is a number between the largest single book pages and the total pages. We binary search this range to find the minimal maximum pages allocation that is feasible.

🔧 Debug

advanced

Identify the Bug in the Allocation Feasibility Check

What error will occur when running this feasibility check function for allocating pages?

DSA Go

func isPossible(books []int, students int, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages >= mid {
            return false
        }
        if sum+pages > mid {
            count++
            sum = pages
            if count > students {
                return false
            }
        } else {
            sum += pages
        }
    }
    return true
}

A It always returns true regardless of input.

B It returns false incorrectly when a book has pages equal to mid, causing wrong allocation.

C It causes an infinite loop.

D It causes a runtime panic due to uninitialized variables.

💡 Hint

Check the condition that compares pages with mid carefully.

The condition 'if pages >= mid' returns false even when pages == mid, but it should allow pages equal to mid. This causes incorrect feasibility results.

❓ Predict Output

advanced

Output of Allocation with 3 Students and 5 Books

What is the output of the following Go code that allocates minimum pages to 3 students for 5 books?

DSA Go

package main
import "fmt"
func isPossible(books []int, students int, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages > mid {
            return false
        }
        if sum+pages > mid {
            count++
            sum = pages
            if count > students {
                return false
            }
        } else {
            sum += pages
        }
    }
    return true
}
func allocateMinimumPages(books []int, students int) int {
    start, end := 0, 0
    for _, pages := range books {
        if pages > start {
            start = pages
        }
        end += pages
    }
    result := end
    for start <= end {
        mid := (start + end) / 2
        if isPossible(books, students, mid) {
            result = mid
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return result
}
func main() {
    books := []int{12, 34, 67, 90, 45}
    students := 3
    fmt.Println(allocateMinimumPages(books, students))
}

A 113

B 101

C 90

D 67

💡 Hint

Try dividing books into 3 parts minimizing the maximum pages assigned.

The optimal allocation is [12,34,67] totaling 113, [90] totaling 90, [45] totaling 45 with max pages 113.

🚀 Application

expert

Minimum Pages Allocation for Large Input with Constraints

Given 7 books with pages [15, 17, 20, 25, 30, 35, 40] and 4 students, what is the minimum maximum pages allocated to any student?

A 70

B 60

C 65

D 55

💡 Hint

Use binary search between max single book pages and sum of all pages to find minimal max allocation.

The minimal maximum pages is 55 by allocating books as [15,17,20], [25,30], [35], [40] or similar grouping.

Practice

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

easy

A. To maximize the total number of pages assigned

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

C. To find the student with the least pages

D. To count the total number of pages in all books

Solution

1. Step 1: Understand the problem objective

   The problem asks to allocate books to students such that the maximum pages assigned to any student is minimized.

2. Step 2: Identify the binary search approach

   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 B

4. Quick Check:

   Goal = minimize max pages [OK]

Hint: Minimize max pages per student using binary search [OK]

Common Mistakes:

• Confusing minimizing max pages with maximizing total pages
• Thinking the problem counts students instead of pages
• Ignoring the binary search on answer approach

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

easy

A. low := 0; high := sum of all pages

B. low := 0; high := max pages in a single book

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

D. low := number of students; high := number of books

Solution

1. Step 1: Determine minimum and maximum boundaries

   The minimum possible max pages is the largest single book pages, because no book can be split.

2. Step 2: Set high boundary as total pages

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

3. Final Answer:

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

4. Quick Check:

   Boundaries = max single book to total pages [OK]

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

Common Mistakes:

• Setting low to 0 which is invalid
• Setting high less than sum of pages
• Confusing number of students with page boundaries

3. Given books with pages [10, 20, 30, 40] and 2 students, what is the minimum maximum pages allocated per student?

medium

A. 40

B. 70

C. 50

D. 60

Solution

1. Step 1: Check possible max pages allocations

   Try max pages = 50: allocation could be [10,20,30] and [40], but first student has 60 pages, which is >50, so invalid.

2. Step 2: Try max pages = 60

   Allocation: [10,20,30] = 60 pages, [40] = 40 pages. Both <= 60, valid allocation.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Try mid values to check feasibility [OK]

Common Mistakes:

• Choosing max single book pages as answer without checking allocation
• Assuming equal split always works
• Not verifying allocation feasibility

4. Identify the bug in this Go code snippet for checking allocation feasibility:

func isPossible(books []int, students int, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages > mid {
            return false
        }
        sum += pages
        if sum > mid {
            count++
            sum = pages
        }
    }
    return count <= students
}

medium

A. No bug, code is correct

B. count should increment before sum addition

C. sum should reset to 0 instead of pages after count++

D. Function should return true if count >= students

Solution

1. Step 1: Analyze sum reset logic

   When sum exceeds mid, count increments and sum resets to current pages, which is correct to start new allocation.

2. Step 2: Check return condition

   Returns true if count of students needed is less than or equal to available students, which is correct.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Sum reset and count logic correct [OK]

Hint: Reset sum to current pages after exceeding mid [OK]

Common Mistakes:

• Resetting sum to 0 instead of current pages
• Returning true when count exceeds students
• Incrementing count too early

5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages allocated? Also, explain why allocating [12, 34] to one student and [67, 90] to another is not optimal.

hard

A. 113; Because max pages is 157 which is more than minimum possible

B. 67; Because 67 is the median of pages

C. 90; Because 90 is the largest single book pages

D. 113; Because max pages is 90 which is less than 113

Solution

1. Step 1: Calculate sum and max single book pages

   Sum = 12+34+67+90 = 203; max single book = 90; low=90, high=203.

2. Step 2: Check allocation with mid = (90+203)/2 = 146

   Try allocation: [12,34,67] = 113 pages, [90] = 90 pages; max = 113 <= 146, feasible.

3. Step 3: Try smaller mid to find minimum max pages

   Try mid=113: allocation same as above, feasible. Try mid=112: allocation fails.

4. Step 4: Explain why [12,34] and [67,90] is not optimal

   Allocation sums: 46 and 157; max is 157 which is greater than minimum max pages 113.

5. Final Answer:

   113; Because max pages is 157 which is more than minimum possible -> Option A

6. Quick Check:

   Minimum max pages = 113; given allocation max = 157 [OK]

Hint: Check allocations sums to find minimal max pages [OK]

Common Mistakes:

• Assuming largest single book pages is answer
• Not verifying allocation sums
• Confusing median with allocation max pages