Allocate minimum number of pages

Question

problem link: https://www.geeksforgeeks.org/allocate-minimum-number-pages/

I understood the concept which uses binary implementation, but not able to find where am going wrong, can someone please help me with this.

link to my code: https://onlinegdb.com/HJu05D2KL

Answer 1

// C++ program for optimal allocation of pages

#include <bits/stdc++.h>

using namespace std;

// Utility function to check if current minimum value

// is feasible or not.

bool isPossible(int arr[], int n, int m, int curr_min)

{

int studentsRequired = 1;

int curr_sum = 0;

// iterate over all books

for (int i = 0; i < n; i++) {

// check if current number of pages are greater

// than curr_min that means we will get the result

// after mid no. of pages

if (arr[i] > curr_min)

return false;

// count how many students are required

// to distribute curr_min pages

if (curr_sum + arr[i] > curr_min) {

// increment student count

studentsRequired++;

// update curr_sum

curr_sum = arr[i];

// if students required becomes greater

// than given no. of students,return false

if (studentsRequired > m)

return false;

}

// else update curr_sum

else

curr_sum += arr[i];

}

return true;

}

// function to find minimum pages

int findPages(int arr[], int n, int m)

{

long long sum = 0;

// return -1 if no. of books is less than

// no. of students

if (n < m)

return -1;

int mx = INT_MIN;

// Count total number of pages

for (int i = 0; i < n; i++) {

sum += arr[i];

mx = max(mx, arr[i]);

}

// initialize start as 0 pages and end as

// total pages

int start = mx, end = sum;

int result = INT_MAX;

// traverse until start <= end

while (start <= end) {

// check if it is possible to distribute

// books by using mid as current minimum

int mid = (start + end) / 2;

if (isPossible(arr, n, m, mid)) {

// update result to current distribution

// as it's the best we have found till now.

result = mid;

// as we are finding minimum and books

// are sorted so reduce end = mid -1

// that means

end = mid - 1;

}

else

// if not possible means pages should be

// increased so update start = mid + 1

start = mid + 1;

}

// at-last return minimum no. of pages

return result;

}

int main()

{

// Number of pages in books

int arr[] = { 12, 34, 67, 90 };

int n = sizeof arr / sizeof arr[0];

int m = 2; // No. of students

    cout << ""

         << findPages(arr, n, m) << endl;

    return 0;

}

// This code is contributed by Aditya Kumar (adityakumar129)

// input

// 1

// 4 2

// 12 34 67 90

Answer 2

#include <iostream>
#include <stdio.h>
using namespace std;

bool findMaxNum(int a[], int numBooks, int numStu, int pageNum) {
    int pageRead = a[0];
    int student = 1;
    for (int i = 1; i < numBooks; i++) {
        if (pageRead + a[i] > pageNum) {
            student++;
            if (student > numStu) {
                return false;
            }
            pageRead = a[i];
        } else {
            pageRead += a[i];
        }
    }
    return true;
}

int main() {
    int testCase;
    cin >> testCase;
    for (int i = 0; i < testCase; i++) {
        int numBooks, numStu;
        cin >> numBooks >> numStu;
        int bukPagesArr[numBooks];
        int sum = 0;
        for (int j = 0; j < numBooks; j++) {
            cin >> bukPagesArr[j];  // each represents number of pages in the jth book
            sum += bukPagesArr[j];
        }
        int start = 0;
        int end = sum;
        int mid;
        int result = -1; // Initialize result to an invalid value
        while (start <= end) {
            mid = (start + end) / 2;
            if (findMaxNum(bukPagesArr, numBooks, numStu, mid)) {
                result = mid; // Update result when condition is satisfied
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        cout << result << endl; //
    }
    return 0;
}