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 i-th chapter has pages[i] pages.
The chapters are arranged 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 = 4pages. Since3 < 4, the student reads till the end of the second chapter – 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 that the student should read each day to finish all chapters within days days.
Complete the minimumNumberOfPages function below.
The function is expected to return an integer.
The function accepts the following parameters:
INTEGER_ARRAY pagesINTEGER days
This problem has a monotonic feasibility structure: if a daily reading limit x is enough to finish within the given number of days, then any larger x is also enough. That makes it a classic binary search on the answer. For each candidate x, compute the required days as the sum of ceiling divisions <code>ceil(pages[i] / x)</code>; if the total is within <code>days</code>, x is feasible. If the number of chapters already exceeds <code>days</code>, the task is impossible because each chapter needs at least one day, so return -1. The intended solution is efficient: <code>O(n log M)</code> with a linear feasibility check.
