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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Pages Allocation for Given Books

What is the output of the following code that finds the minimum number of pages to allocate to 2 students from the given books array?

DSA Python

def is_possible(arr, n, m, mid):
    student_count = 1
    page_sum = 0
    for i in range(n):
        if arr[i] > mid:
            return False
        if page_sum + arr[i] > mid:
            student_count += 1
            page_sum = arr[i]
            if student_count > m:
                return False
        else:
            page_sum += arr[i]
    return True

def find_pages(arr, n, m):
    start = max(arr)
    end = sum(arr)
    result = end
    while start <= end:
        mid = (start + end) // 2
        if is_possible(arr, n, m, mid):
            result = mid
            end = mid - 1
        else:
            start = mid + 1
    return result

books = [12, 34, 67, 90]
students = 2
print(find_pages(books, len(books), students))

A 157

B 113

C 90

D 67

💡 Hint

Think about how the binary search narrows down the maximum pages a student can get.

The minimum maximum pages allocated to 2 students is 113. The allocation can be [12, 34, 67] and [90], where the maximum pages assigned is 113.

🧠 Conceptual

intermediate

Understanding the Role of 'mid' in Binary Search Allocation

In the binary search approach to allocate minimum pages, what does the variable 'mid' represent?

A The total number of pages in all books combined

B The number of students to allocate books to

C The minimum number of pages a student must get

D The maximum number of pages a single student can be allocated in the current check

💡 Hint

Consider what the binary search is trying to minimize or maximize.

'mid' is the candidate maximum pages that a student can be assigned. The algorithm checks if allocation is possible without exceeding 'mid'.

🔧 Debug

advanced

Identify the Error in Allocation Check Function

What error will the following code produce when running the allocation check for books = [10, 20, 30], students = 2, mid = 25?

DSA Python

def is_possible(arr, n, m, mid):
    student_count = 1
    page_sum = 0
    for i in range(n):
        if arr[i] > mid:
            return False
        if page_sum + arr[i] >= mid:
            student_count += 1
            page_sum = arr[i]
            if student_count > m:
                return False
        else:
            page_sum += arr[i]
    return True

print(is_possible([10, 20, 30], 3, 2, 25))

A Returns False

B Returns True

C IndexError

D Infinite loop

💡 Hint

Check the condition that triggers a new student allocation.

The condition 'page_sum + arr[i] >= mid' causes the allocation to split too early, making it impossible to allocate within mid=25, so it returns False.

❓ Predict Output

advanced

Output of Allocation with Multiple Students and Books

What is the output of the code below for books = [10, 20, 30, 40, 50], students = 3?

DSA Python

def is_possible(arr, n, m, mid):
    student_count = 1
    page_sum = 0
    for i in range(n):
        if arr[i] > mid:
            return False
        if page_sum + arr[i] > mid:
            student_count += 1
            page_sum = arr[i]
            if student_count > m:
                return False
        else:
            page_sum += arr[i]
    return True

def find_pages(arr, n, m):
    start = max(arr)
    end = sum(arr)
    result = end
    while start <= end:
        mid = (start + end) // 2
        if is_possible(arr, n, m, mid):
            result = mid
            end = mid - 1
        else:
            start = mid + 1
    return result

books = [10, 20, 30, 40, 50]
students = 3
print(find_pages(books, len(books), students))

A 70

B 90

C 60

D 100

💡 Hint

Try to split books into 3 groups minimizing the maximum pages per student.

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

🧠 Conceptual

expert

Why Binary Search is Used in Allocate Minimum Pages Problem

Why is binary search an efficient approach to solve the Allocate Minimum Pages problem instead of a brute force approach?

A Because the answer lies in a sorted range of possible maximum pages and binary search reduces the search space efficiently

B Because binary search can directly find the exact allocation without checking conditions

C Because the problem requires sorting the books array first

D Because binary search is the only algorithm that can handle arrays

💡 Hint

Think about how the maximum pages range is bounded and how binary search narrows it down.

The maximum pages a student can get lies between the max single book pages and the sum of all pages. Binary search efficiently narrows this range by checking feasibility.

Practice

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

easy

A. To find the minimum maximum number of pages assigned to a student

B. To maximize the total pages assigned to all students

C. To find the maximum number of students that can be assigned books

D. To minimize the total number of books assigned

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify the binary search target

   Binary search is used on the range of possible maximum pages to find the smallest feasible maximum.

3. Final Answer:

   To find the minimum maximum number of pages assigned to a student -> Option A

4. Quick Check:

   Minimum max pages = goal [OK]

Hint: Focus on minimizing the largest pages any student gets [OK]

Common Mistakes:

• Confusing total pages with maximum pages per student
• Trying to maximize pages instead of minimizing
• 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 given an array pages of book pages?

easy

A. low = sum(pages), high = max(pages)

B. low = max(pages), high = sum(pages)

C. low = 0, high = max(pages)

D. low = 0, high = sum(pages) * 2

Solution

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

   The minimum max pages is at least the largest single book (max of pages), and the maximum is the sum of all pages if one student gets all books.

2. Step 2: Set binary search boundaries accordingly

   Set low = max(pages) and high = sum(pages) to cover all feasible max page values.

3. Final Answer:

   low = max(pages), high = sum(pages) -> Option B

4. Quick Check:

   Boundaries = max and sum [OK]

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

Common Mistakes:

• Setting low to 0 which is invalid
• Swapping low and high values
• Using arbitrary high value instead of sum

3. What will be the output of the following code snippet?

def is_possible(pages, students, mid):
    count = 1
    total = 0
    for p in pages:
        if total + p > mid:
            count += 1
            total = p
            if count > students:
                return False
        else:
            total += p
    return True

pages = [10, 20, 30, 40]
students = 2
mid = 50
print(is_possible(pages, students, mid))

medium

A. True

B. None

C. SyntaxError

D. False

Solution

1. Step 1: Trace the allocation with mid = 50

   pages=[10,20,30,40], students=2: count=1, total=0 - p=10: total=10 <=50 - p=20: total=30 <=50 - p=30: 30+30=60 >50 -> count=2, total=30 - p=40: 30+40=70 >50 -> count=3 >2 -> return False

2. Step 2: Check if count exceeds students

   Count reaches 3 > 2, so return False.

3. Final Answer:

   False -> Option D

4. Quick Check:

   Allocation not possible with mid=50 = False [OK]

Hint: Check if books fit in mid pages per student [OK]

Common Mistakes:

• Miscounting students needed
• Adding pages incorrectly
• Confusing > and >= in condition

4. Identify the bug in the following code snippet for the Allocate Minimum Pages problem:

def allocate_pages(pages, students):
    low = max(pages)
    high = sum(pages)
    result = 0
    while low <= high:
        mid = (low + high) // 2
        if is_possible(pages, students, mid):
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result

medium

A. The high pointer should move to mid - 1 when allocation is possible

B. The low pointer should move to mid + 1 when allocation is possible

C. The low pointer should move to mid when allocation is possible

D. The low pointer should move to mid - 1 when allocation is not possible

Solution

1. Step 1: Understand binary search update rules

   If allocation is possible at mid, we try to find smaller max pages by moving high to mid - 1. If not possible, we increase low to mid + 1.

2. Step 2: Identify incorrect pointer update

   The code incorrectly moves low to mid + 1 when allocation is possible instead of high to mid - 1, which searches larger values instead of smaller.

3. Final Answer:

   The high pointer should move to mid - 1 when allocation is possible -> Option A

4. Quick Check:

   Move high down when allocation succeeds [OK]

Hint: Move low up only when allocation fails, else move high down [OK]

Common Mistakes:

• Swapping low and high updates
• Not updating pointers correctly causing infinite loop
• Returning wrong result due to pointer errors

5. Given the books with pages [12, 34, 67, 90] and 3 students, what is the minimum possible maximum number of pages assigned to a student using binary search on answer?

hard

A. 67

B. 113

C. 90

D. 34

Solution

1. Step 1: Set binary search boundaries

   low = max(pages) = 90, high = sum(pages) = 203.

2. Step 2: Check feasibility at mid values

   Try mid = (90+203)//2 = 146: count=1, total=0 - p=12: total=12 <=146 - p=34: total=46 <=146 - p=67: total=113 <=146 - p=90: 113+90=203 >146 -> count=2, total=90 count=2 <=3, possible -> try smaller max Try mid = (90+145)//2 = 117: count=1, total=0 - p=12: total=12 <=117 - p=34: total=46 <=117 - p=67: total=113 <=117 - p=90: 113+90=203 >117 -> count=2, total=90 count=2 <=3, possible -> try smaller max Try mid = (90+116)//2 = 103: count=1, total=0 - p=12: total=12 <=103 - p=34: total=46 <=103 - p=67: 46+67=113 >103 -> count=2, total=67 - p=90: 67+90=157 >103 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+102)//2 = 96: count=1, total=0 - p=12: total=12 <=96 - p=34: total=46 <=96 - p=67: 46+67=113 >96 -> count=2, total=67 - p=90: 67+90=157 >96 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+95)//2 = 92: count=1, total=0 - p=12: total=12 <=92 - p=34: total=46 <=92 - p=67: 46+67=113 >92 -> count=2, total=67 - p=90: 67+90=157 >92 -> count=3, total=90 count=3 <=3, possible -> try smaller max Try mid = (90+91)//2 = 90: count=1, total=0 - p=12: total=12 <=90 - p=34: total=46 <=90 - p=67: 46+67=113 >90 -> count=2, total=67 - p=90: 67+90=157 >90 -> count=3, total=90 count=3 <=3, possible Try mid = (90+89)//2 = 89 (low > high, stop) Minimum max pages = 90

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Minimum max pages = 90 [OK]

Hint: Binary search between max single book and total pages sum [OK]

Common Mistakes:

• Choosing max single book as answer without checking feasibility
• Not updating low and high correctly during binary search
• Misallocating books to students during checks