Allocate Books in java

Problem Description

Given an array of integers A of size N and an integer B.

College library has N bags,the ith book has A[i] number of pages.

You have to allocate books to B number of students so that maximum number of pages alloted to a student is minimum.

A book will be allocated to exactly one student. Each student has to be allocated at least one book. Allotment should be in contiguous order, for example: A student cannot be allocated book 1 and book 3, skipping book 2. Calculate and print that minimum possible number.

NOTE: Print -1 if a valid assignment is not possible.

Input Format

The first line given is an integer N, denoting the size of array A. The second line given is the integer array A. The third line given is the integer B.

Output Format

Print that minimum possible number

Constraints

1 <= N <= 10^5 1 <= A[i] <= 10^5

For Example

Input 1: 4 12 34 67 90 2

Output 1: 113

Explanation 1: There are 2 number of students. Books can be distributed in following fashion : 1) [12] and [34, 67, 90] Max number of pages is allocated to student 2 with 34 + 67 + 90 = 191 pages 2) [12, 34] and [67, 90] Max number of pages is allocated to student 2 with 67 + 90 = 157 pages 3) [12, 34, 67] and [90] Max number of pages is allocated to student 1 with 12 + 34 + 67 = 113 pages

    Of the 3 cases, Option 3 has the minimum pages = 113.

Input 2: 4 5 17 100 11 4

Output 2: 100

Solution of Allocate Books in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
                int n, b;
                // b is the number of students
                Scanner sc = new Scanner(System.in);
                n = sc.nextInt();
                int pages[] = new int[n];
                long sum = 0;
                for(int i = 0; i < n; i++) {
                        pages[i] = sc.nextInt();
                        sum += pages[i];
                }
                b = sc.nextInt();
                if(b > n){
                        // not enough books for each student
                        System.out.println(-1);
                        return;
                }
                long ans = -1, l = 0, r = sum;
                long mid;
                while(l <= r){
                        mid = (l + r) / 2;
                        if(isValid(pages, n, b, mid) == true){
                                ans = mid;
                                r = mid - 1;
                        }
                        else{
                                l = mid + 1;
                        }
                }
                System.out.println(ans);
	}
        static boolean isValid(int pages[], int n, int b, long max){
                // In this case, 
                // maximum number of pages allowed per student is max
                long sum = 0, students = 1;
                for(int i = 0; i < n; i++){ // for all the books
                        sum += pages[i];
                        // if sum remains less than max -> I should keep 
                        if(sum > max){ // the student got more pages than we allow
                                students++;
                                sum = pages[i]; // sum = number of pages in ith book
                                if(pages[i] > max) // this particular book in itself has
                                        return false;
                        }
                        if(students > b)
                                return false;
                }
                // The number of students, didn't exceed b
                return true;
        }
}