Top Amazon Questions | Level up your coding skills and quickly land a job

2 Live

A student is preparing for a scholarship test which is organized on the Amazon Academy platform and scheduled for next month. There are n chapters to be studied where the ith chapter has pages[i] pages. In one day, the student decides to read up to p of the remaining pages, each from some k consecutive chapters. Thus, the number of pages remaining to be read is reduced by p from each of these chapters. If a chapter has less than p pages remaining, the student reads the remaining pages, and the remaining page count is set to 0 for subsequent days. Find the minimum number of days the student needs to read all the chapters completely, i.e., the remaining page count of all chapters is 0. Note: The chapters read must be contiguous. Example The number of chapters is n = 3, the number of chapters read in a day is k = 2, the number of pages read from each chapter is p = 2, and the page counts of each chapter are pages = [3, 1, 4]. The chapters can be read as follows: Chapters read must be contiguous. - Choose chapters 1 and 2, remaining pages to be read = [1, 0, 4]. - Choose chapters 1 and 2, remaining pages to be read = [0, 0, 4]. - Choose chapters 2 and 3, remaining pages to be read = [0, 0, 2]. - Finally, choose chapters 2 and 3, remaining pages to be read = [0, 0, 0]. The chapters cannot be read in less than 4 days. Function Description Complete the function findMinimumDays in the editor below. findMinimumDays has the following parameters: int pages[n]: the number of pages in each chapter int k: the number of chapters chosen each day int p: the maximum number of pages read from Returns long_int: the minimum number of days to read all pages of all chapters Constraints - 1 ≤ n ≤ 10^5 - 1 ≤ pages[i] ≤ 10^9 - 1 ≤ k ≤ n - 1 ≤ p ≤ 10^9 Input Format For Custom Testing Sample Case 0 Sample Input For Custom Testing STDIN 2 FUNCTION 3 4 1 2 pages[] size n = 2 pages = [3, 4] k = 1 p = 2 Sample Output 4 Explanation Read the first chapter for the first two days, and the second chapter for the next two days. Sample Case 1 Sample Input For Custom Testing STDIN FUNCTION 3 5 pages[] size n = 3 pages = [5, 1, 2] 1 2 3 3 k = 3 p = 3 Sample Output 2 Explanation After 1st day, the number of pages remaining = [2, 0, 0]. After 2nd day, the number of pages remaining = [0, 0, 0].

Asked in: AMAZON

Image of the Question

All Testcases Passed ✔

Solution

def findMinimumDays(pages, k, p):
    # Write your code here
    n = len(pages)
    arr = [0 for i in range(n+k+2)]
// ... rest of solution available after purchase

🔒 Please login to view the solution

Explanation

```
To approach this problem, you need to carefully analyze the constraints and the rules governing how the student reads the chapters, then devise a strategy that calculates the minimum number of days required efficiently, considering the potentially large input sizes.

---

### Step 1: Understanding the problem setup

You have:
- **n** chapters, each with a certain number of pages (pages[i]).
- Every day, the student chooses **k** contiguous chapters to read.
- From each of these chosen chapters, the student reads up to **p** pages. If the chapter has fewer than p pages remaining, all remaining pages are read, reducing that chapter’s remaining pages to zero.
- The goal is to minimize the number of days required to finish reading all chapters entirely (all pages reduced to zero).

Important points:
- The chapters chosen on any given day must be contiguous.
- Reading from k chapters means reducing pages of those k chapters simultaneously by up to p pages each.
- The student can choose different contiguous segments on different days.

---

### Step 2: Intuition about the problem

At first glance, the problem looks complex due to:
- Large number of chapters (up to 10^5).
- Possibly huge page counts (up to 10^9 per chapter).
- The necessity to choose contiguous chapters each day, and read p pages from each of these chapters.

Because the student reads from k consecutive chapters simultaneously, each day reduces the remaining pages in those k chapters by p.

---

### Step 3: What does one day do?

- One day of reading reduces pages of a contiguous block of length k by p pages each.
- If a chapter in the chosen block has fewer than p pages left, it is reduced to zero.
- Over multiple days, the student can choose different contiguous blocks to reduce the remaining pages strategically.

---

### Step 4: Core challenge: How to cover all chapters efficiently?

You need to pick contiguous segments of length k repeatedly, reducing pages until all chapters are finished.

The problem then reduces to:
- Covering the array of chapters with these segments so that the total reduction applied to each chapter equals or exceeds its initial page count.
- Minimize the number of days (operations) to achieve this.

---

### Step 5: Key observations

1. **Coverage frequency per chapter:**
Each chapter can be covered multiple times (on different days) by these segments.
For example, if k=2 and n=5, chapter 3 can be covered by segments [1,2], [2,3], [3,4], or [4,5], depending on the choices each day.

2. **The number of times a chapter needs to be "covered" (read from) to finish:**
If a chapter has pages[i] pages, and each day when chosen it is reduced by p pages, then minimum number of days this chapter must be chosen is:

days_for_chapter = ceil(pages[i] / p)

3. **How can days be arranged so that all chapters reach zero?**

Because the reading must be done in contiguous segments of length k, a key question is: what is the minimal total number of days to collectively cover all chapters with these segments such that each chapter is covered enough times?

---

### Step 6: Interpreting the problem as a covering or scheduling problem

- Each day corresponds to choosing one contiguous segment of length k.
- Each segment covers k chapters and applies one unit of reading (p pages reduction).
- A chapter needs to be covered at least `days_for_chapter` times.
- Need to arrange minimal days (segments) to cover all chapters with the required number of coverage.

---

### Step 7: Lower bound estimation on days

- Since every day reduces p pages for k chapters, the maximum pages reduced per day is `k * p`.
- Total pages to be read are sum of pages in all chapters.
- So, a minimal number of days needed is at least:

total_pages / (k * p)

- But this is a rough lower bound, because:
- You can’t always perfectly pack coverage due to the contiguous constraint.
- Some chapters might require more coverage because they have more pages.

---

### Step 8: Important insight from problem constraints

Because reading segments must be contiguous and fixed length k, the problem resembles a "sliding window" coverage problem:
- The student can select any contiguous window of size k to reduce pages on a day.
- The total number of days corresponds to how many such windows (possibly overlapping) must be chosen to cover all chapters sufficiently.

---

### Step 9: Approaching the problem with a binary search on the answer

Given the complexity, a common approach is to **guess the answer** (number of days) and check if it is feasible.

- Suppose you guess D days.
- Then you want to know if it's possible to schedule D contiguous k-length segments (with possible overlaps) to cover every chapter i at least `days_for_chapter` times.
- If yes, try a smaller D.
- If no, try a larger D.

This approach uses binary search over the number of days because the minimum days must be between 1 and some upper bound (like sum of days_for_chapter or sum of pages divided by p).

---

### Step 10: How to check feasibility for a guess D?

- You want to assign the D segments to cover the chapters so that each chapter is covered at least the required number of times.
- Since each segment covers exactly k consecutive chapters, the problem reduces to distributing D segments over the n chapters such that:

coverage[i] = number of segments covering chapter i ≥ days_for_chapter[i]

- Because segments are length k and contiguous, coverage forms a kind of "interval coverage" over the chapters.
- You need to decide if there exists a sequence of D intervals of length k covering the chapters with these minimum coverage requirements.

---

### Step 11: How to represent coverage and constraints?

- Imagine an array coverage of length n initialized to zero.
- Each selected segment of length k adds +1 coverage to chapters in its range.
- After selecting D segments, coverage[i] = number of times chapter i is covered.
- The problem: Can you find coverage assignments from D segments (intervals of length k) such that coverage[i] ≥ days_for_chapter[i] for all i?

---

### Step 12: Using prefix sums or greedy checks

Checking feasibility for a given D can be tricky, but with prefix sums and greedy approaches you might:

- Try to greedily place segments from left to right to meet the coverage demands.
- Or translate coverage requirements into constraints on how many segments overlap at each position.
- Because each segment adds coverage of 1 to a range of length k, coverage increments can be modeled as range additions.

If the total required coverage sum ≤ D * k (because each segment covers k chapters), it might be feasible, but arrangement constraints must be respected.

---

### Step 13: Algorithmic outline

1. Compute days_for_chapter[i] = ceil(pages[i] / p) for all chapters.
2. Set left = 1, right = max(days_for_chapter) * n or sum(days_for_chapter) (upper bound).
3. While left < right:
- mid = (left + right) / 2
- Check if mid days suffice to cover all chapters with required coverage.
- If feasible, right = mid
- Else left = mid + 1
4. Return left.

---

### Step 14: Final remarks

- The main complexity lies in checking feasibility efficiently.
- You may need to use a sliding window approach or greedy interval coverage to assign segments.
- The problem transforms into a coverage scheduling problem where intervals have fixed length k, and you must meet minimum coverage counts per position.
- The binary search helps because naive approaches would be too slow for large inputs.
- Efficient prefix sums or segment trees might help during feasibility checks.

---

### Summary

- Transform page counts into days required per chapter.
- Understand daily reading reduces pages of k contiguous chapters by p.
- Use binary search on days to guess minimal total days.
- For a guess, check if coverage by D intervals of length k meets chapter requirements.
- Employ greedy or prefix sum methods for feasibility.
- Return the minimum days found by binary search.

This strategy ensures that you efficiently handle large inputs and constraints while capturing the contiguous reading restriction and page reduction mechanism.
```