A student is preparing for a test from Amazon Academy for a scholarship. The student is required to completely read n chapters for the test where the ith chapter has pages[i] number of pages. The chapters are read in Increasing order of the index. Each day the student can either read till the end of a chapter or at most x pages, whichever is minimum. The number of pages remaining to read decreases by x in the latter case.
For example, If pages = [5, 3, 4] and x = 4


• Day 1: The student reads 4 pages of the first chapter – pages remaining = [1, 3, 4]
• Day 2: The student can only read till the end of the first chapter – pages remaining = [0, 3, 4]
• Day 3: The student can read either till the end of the chapter or x = 4 pages, since 3 <4, the student reads till the end of the chapter 2 – pages remaining = [0, 0, 4]
• Day 4: The student reads all the 4 pages of the last chapter – pages remaining – [0, 0,0]
The test will be given in days number of days from now. Find the minimum number of pages, x, which the student should read each day to finish all pages of all chapters within days number of days. If It Is not possible to finish these chapters in days number of days, return -1.


Note: In one day, the student cannot read pages of more than one chapter. Thus, if a chapter finishes, the next chapter starts only on the next day even If the number of pages read is less than x.

Function Description
Complete the function findMinimumNumberOfPages in the editor below.
findMinimumNumberOfPages has the following parameters:
int pages[n]: the number of pages in each chapter int days. the maximum number of days
Returns
int: the minimum number of pages to be read each day, or -1 if it is not possible to finish
Constraints
• 1 ≤ n ≤ 105
• 1 ≤ days ≤ 109
• 1 ≤ pages[i] ≤ 104

SAMPLE TEST CASE

pages[] size n=4

pages = [2,3,4,5];

days =5

If x = 4, the student would read the 1st, 2nd and 3rd chapters in 1 day each, and the 4th chapter in 2 days. The total number of days taken = 1 + 1 + 1 + 2 = 5, which is within the number of allowed days. If x is less than 4, the chapters cannot be finished within 5 days.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static boolean canFinishReading(List<Integer> pages, int days, int x) {
        int totalDays = 0;
        for (int pageCount : pages) {
            int daysNeeded = pageCount / x;
            if (pageCount % x != 0) {
                daysNeeded += 1;
            }
            totalDays += daysNeeded;
        }
        return totalDays <= days;
    }

    public static void main(String[] args) {
        List<Integer> pages = new ArrayList<>();
        pages.add(2);
        pages.add(3);
        pages.add(4);
        pages.add(5);
        int days = 5;
        int maxPages = pages.stream().mapToInt(Integer::intValue).max().orElse(0);

        int result = -1;
        for (int x = 1; x <= maxPages; x++) {
            if (canFinishReading(pages, days, x)) {
                result = x;
                break;
            }
        }
        System.out.println(result);
    }
}

Categorized in: