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.