Bird
Raised Fist0
DSA Cprogramming~5 mins

Allocate Minimum Pages Binary Search on Answer in DSA C - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Allocate Minimum Pages Binary Search on Answer
O(n log S)
Understanding Time Complexity

We analyze how the time needed grows when we try to allocate pages to students using binary search on the answer.

We want to know how the number of steps changes as the number of books and pages increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


int 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] <= mid) {
            pageSum += arr[i];
        } else {
            studentCount++;
            pageSum = arr[i];
            if (studentCount > m) return 0;
        }
    }
    return 1;
}

int allocatePages(int arr[], int n, int m) {
    int start = 0, end = 0;
    for (int i = 0; i < n; i++) {
        if(arr[i] > start) start = arr[i];
        end += arr[i];
    }
    int result = -1;
    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;
}

This code tries to find the minimum maximum pages assigned to students by using binary search on the possible page range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The while loop performing binary search on the page range.
  • Nested operation: The for loop inside isPossible that checks if allocation is possible.
  • How many times: The binary search loop runs about log(sum of pages) times, and each time it runs the for loop over all n books.
How Execution Grows With Input

As the number of books or total pages grows, the binary search steps grow slowly, but each step checks all books.

Input Size (n)Approx. Operations
10 books, sum pages ~1000~10 * log(1000) ≈ 10 * 10 = 100
100 books, sum pages ~10000~100 * log(10000) ≈ 100 * 14 = 1400
1000 books, sum pages ~100000~1000 * log(100000) ≈ 1000 * 17 = 17000

Pattern observation: The total steps grow roughly by multiplying the number of books by the logarithm of total pages.

Final Time Complexity

Time Complexity: O(n log S)

This means the time grows linearly with the number of books and logarithmically with the total pages.

Common Mistake

[X] Wrong: "The binary search alone makes this algorithm run in logarithmic time."

[OK] Correct: Each binary search step requires checking all books, so the total time multiplies the linear check by the logarithmic steps.

Interview Connect

Understanding this time complexity helps you explain how binary search can be used on answers, a common pattern in problem solving.

It shows your ability to combine searching with validation steps efficiently.

Self-Check

"What if we replaced the linear check in isPossible with a more efficient method? How would that affect the time complexity?"

Practice

(1/5)
1. What is the main goal of the Allocate Minimum Pages problem when using binary search on the answer?
easy
A. To maximize the total number of pages assigned
B. To find the average number of pages per student
C. To minimize the maximum number of pages assigned to any student
D. To assign pages randomly to students

Solution

  1. Step 1: Understand the problem goal

    The problem wants to divide 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 any student -> Option C

  4. Quick Check:

    Goal = minimize max pages per student [OK]
Hint: Focus on minimizing the max pages per student, not total pages [OK]
Common Mistakes:
  • Confusing total pages with maximum pages per student
  • Thinking binary search finds average pages
  • Assuming random assignment solves the problem
2. Which of the following is the correct way to initialize the binary search range for the Allocate Minimum Pages problem in C?
easy
A. int low = max_page_count, high = sum_of_all_pages;
B. int low = 0, high = sum_of_all_pages;
C. int low = 0, high = max_page_count;
D. int low = sum_of_all_pages, high = max_page_count;

Solution

  1. Step 1: Determine the search boundaries

    The minimum possible max pages is at least the largest single book (max_page_count), and the maximum possible is the sum of all pages.

  2. Step 2: Set binary search range accordingly

    So, low = max_page_count and high = sum_of_all_pages is correct initialization.

  3. Final Answer:

    int low = max_page_count, high = sum_of_all_pages; -> Option A

  4. Quick Check:

    low = max single book, high = total pages [OK]
Hint: Start low at max single book pages, high at total pages sum [OK]
Common Mistakes:
  • Starting low at 0 instead of max book pages
  • Swapping low and high values
  • Using arbitrary values outside page counts
3. Given the array of pages [10, 20, 30, 40] and 2 students, what is the minimum maximum pages assigned to a student?
medium
A. 30
B. 50
C. 40
D. 60

Solution

  1. Step 1: Check possible max pages assignments

    Try to split books into 2 parts so max pages per student is minimized. Possible splits: [10,20,30] and [40] max 60; [10,20] and [30,40] max 70; [10,20,30,40] all to one student max 100.

  2. Step 2: Use binary search or reasoning

    Splitting as [10,20] and [30,40] gives max 70, but [10,20,30] and [40] gives max 60. Check if 50 is possible: [10,20] and [30,40] max 70 too high, but [10,20,30] is 60. So 50 is not possible because 40 > 50. So minimum max pages is 60.

  3. Final Answer:

    60 -> Option D

  4. Quick Check:

    Minimum max pages = 60 [OK]
Hint: Try splitting books to minimize max pages per student [OK]
Common Mistakes:
  • Choosing max single book as answer without checking splits
  • Assuming equal split always works
  • Ignoring that a student must get continuous books
4. Identify the error in this C code snippet for checking feasibility in Allocate Minimum Pages problem: 
int isPossible(int arr[], int n, int m, int mid) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pageSum + arr[i] <= mid) {
            pageSum += arr[i];
        } else {
            studentCount++;
            pageSum = arr[i];
        }
    }
    return studentCount <= m;
}
medium
A. It does not check if a single book has more pages than mid
B. It increments studentCount incorrectly
C. It should return studentCount >= m instead
D. It does not initialize pageSum to arr[0]

Solution

  1. Step 1: Analyze feasibility check logic

    The function tries to assign books to students without exceeding mid pages per student.

  2. Step 2: Identify missing check

    If a single book has pages more than mid, the function still tries to assign it, which is invalid. This case is not handled.

  3. Final Answer:

    It does not check if a single book has more pages than mid -> Option A

  4. Quick Check:

    Check single book pages <= mid [OK]
Hint: Always check if any book exceeds mid before assigning [OK]
Common Mistakes:
  • Ignoring single book size check
  • Returning wrong comparison for studentCount
  • Incorrect initialization of pageSum
5. You have books with pages [12, 34, 67, 90] and 2 students. Using binary search on answer, what is the minimum maximum pages a student can get? Explain the steps.
hard
A. 101
B. 113
C. 90
D. 67

Solution

  1. Step 1: Set binary search range

    Minimum max pages = max single book = 90, maximum = sum = 12+34+67+90=203.

  2. Step 2: Apply binary search and feasibility check

    Mid = (90+203)/2=146. Check if possible with max 146 pages: assign [12,34,67] sum=113 to student1, [90] to student2. Possible. Try lower mid.

  3. Step 3: Narrow down mid

    Mid = (90+146)/2=118. Check with 118: assign [12,34,67] sum=113 student1, [90] student2. Possible. Try lower mid.

  4. Step 4: Check mid=104

    Assign [12,34] sum=46 student1, [67,90] sum=157 student2 exceeds 104. Not possible.

  5. Step 5: Check mid=111

    Assign [12,34,67] sum=113 >111 no. Assign [12,34] sum=46 student1, [67,90] sum=157 no. Not possible.

  6. Step 6: Check mid=113

    Assign [12,34,67] sum=113 student1, [90] student2. Possible.

  7. Step 7: Final minimum max pages

    Minimum max pages = 113.

  8. Final Answer:

    113 -> Option B

  9. Quick Check:

    Minimum max pages = 113 [OK]
Hint: Use binary search between max single book and total pages [OK]
Common Mistakes:
  • Choosing max single book as answer without checking splits
  • Not testing feasibility properly
  • Confusing sum and max in binary search range
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard