Bird
Raised Fist0
DSA C++programming~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(sum_of_pages))
Understanding Time Complexity

We want to find how fast the binary search approach works to allocate minimum pages among students.

How does the number of operations grow as the number of books or pages increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


bool 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];
            if (studentCount > m || arr[i] > mid) return false;
        }
    }
    return true;
}

int allocateMinimumPages(int arr[], int n, int m) {
    int start = 0, end = 0, result = -1;
    for (int i = 0; i < n; i++) end += arr[i];
    while (start <= end) {
        int mid = start + (end - start) / 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 a student can get by using binary search on the answer space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The binary search loop runs repeatedly, and inside it, the isPossible function traverses the array once.
  • How many times: Binary search runs about log of the sum of pages times, and isPossible runs once per binary search step, traversing all books (n times).
How Execution Grows With Input

As the number of books (n) or total pages increases, the binary search tries fewer guesses than checking all possibilities.

Input Size (n)Approx. Operations
10About 10 * log(sum of pages)
100About 100 * log(sum of pages)
1000About 1000 * log(sum of pages)

Pattern observation: Operations grow linearly with number of books and logarithmically with total pages.

Final Time Complexity

Time Complexity: O(n * log(sum_of_pages))

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

Common Mistake

[X] Wrong: "The binary search runs in O(log n) time because it halves the input size each time."

[OK] Correct: The binary search here is on the range of possible page sums, not on the number of books. Each step requires checking all books, so the array traversal makes it O(n * log(sum_of_pages)).

Interview Connect

Understanding this time complexity helps you explain how binary search can be applied beyond sorted arrays, showing problem-solving flexibility.

Self-Check

"What if we used a linear search instead of binary search on the answer range? How would the time complexity change?"

Practice

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

Solution

  1. Step 1: Understand the problem objective

    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: Recognize the use of binary search on answer

    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 D

  4. Quick Check:

    Goal = minimize max pages per student [OK]
Hint: Focus on minimizing the largest pages assigned [OK]
Common Mistakes:
  • Thinking it maximizes total pages
  • Confusing average with maximum
  • Ignoring the binary search approach
2. Which of the following is the correct way to initialize the binary search boundaries for the Allocate Minimum Pages problem in C++?
easy
A. int low = max pages in a single book, high = sum of all pages;
B. int low = 0, high = sum of all pages;
C. int low = 0, high = max pages in a single book;
D. int low = sum of all pages, high = max pages in a single book;

Solution

  1. Step 1: Determine the minimum and maximum boundaries

    The minimum possible max pages is the largest single book (no student can get less than that), and the maximum is the sum of all pages (one student gets all books).

  2. Step 2: Set binary search boundaries accordingly

    So, low = max pages in a single book, high = sum of all pages.

  3. Final Answer:

    int low = max pages in a single book, high = sum of all pages; -> Option A

  4. Quick Check:

    low = max single book, high = total pages [OK]
Hint: Low = max single book pages, High = sum of all pages [OK]
Common Mistakes:
  • Setting low to 0 which is invalid
  • Swapping low and high values
  • Using average pages as boundary
3. What will be the output of the following C++ code snippet for the Allocate Minimum Pages problem?
int pages[] = {10, 20, 30, 40};
int n = 4, students = 2;

// Function to check feasibility
bool isPossible(int mid) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pages[i] > mid) return false;
        if (pageSum + pages[i] > mid) {
            studentCount++;
            pageSum = pages[i];
            if (studentCount > students) return false;
        } else {
            pageSum += pages[i];
        }
    }
    return true;
}

int low = 40, high = 100, result = high;
while (low <= high) {
    int mid = (low + high) / 2;
    if (isPossible(mid)) {
        result = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}
std::cout << result << std::endl;
medium
A. 50
B. 70
C. 60
D. 40

Solution

  1. Step 1: Understand the feasibility check

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

  2. Step 2: Binary search to find minimum max pages

    Try mid values between 40 and 100. The minimum feasible max pages is 60 (assign {10,20,30} to student 1 and {40} to student 2).

  3. Final Answer:

    60 -> Option C

  4. Quick Check:

    Minimum max pages = 60 [OK]
Hint: Check feasibility by simulating allocation [OK]
Common Mistakes:
  • Not updating student count correctly
  • Choosing mid incorrectly
  • Ignoring single book page size
4. Identify the bug in the following C++ code snippet for the Allocate Minimum Pages problem:
bool isPossible(int mid, int pages[], int n, int students) {
    int studentCount = 1, pageSum = 0;
    for (int i = 0; i < n; i++) {
        if (pageSum + pages[i] <= mid) {
            pageSum += pages[i];
        } else {
            studentCount++;
            pageSum = pages[i];
        }
    }
    return studentCount <= students;
}
medium
A. Missing check if a single book has pages more than mid
B. Incorrect increment of studentCount
C. Page sum should reset to zero instead of pages[i]
D. Loop should run from i = 1 instead of 0

Solution

  1. Step 1: Analyze the feasibility function

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

  2. Step 2: Identify missing validation

    It does not check if any single book has pages more than mid, which makes allocation impossible.

  3. Final Answer:

    Missing check if a single book has pages more than mid -> Option A

  4. Quick Check:

    Check single book pages <= mid [OK]
Hint: Always check single book pages against mid [OK]
Common Mistakes:
  • Ignoring single book size check
  • Resetting pageSum incorrectly
  • Wrong loop start index
5. Given the books with pages {12, 34, 67, 90} and 2 students, what is the minimum maximum number of pages a student can get when using binary search on answer to allocate books optimally?
hard
A. 90
B. 113
C. 101
D. 67

Solution

  1. Step 1: Set binary search boundaries

    Low = max single book = 90, High = sum = 12+34+67+90=203.

  2. Step 2: Use binary search to find minimum max pages

    Check mid values. The minimum feasible max pages is 113 (assign {12,34,67}=113 to one student and {90} to the other).

  3. Final Answer:

    113 -> Option B

  4. Quick Check:

    Minimum max pages = 113 [OK]
Hint: Binary search between max single book and total pages [OK]
Common Mistakes:
  • Choosing max single book as answer
  • Choosing sum of pages as answer
  • Not testing feasibility properly
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