Amazon OA question

A student needs to read n chapters for a scholarship test. The number of pages in each chapter is given in an array pages. Each day, the student chooses k consecutive chapters and reads up to p pages from each of these chosen chapters. If a chapter has fewer than p pages remaining, the student reads all the remaining pages of that chapter. The goal is to find the minimum number of days required to read all the pages of all chapters (i.e., until the remaining page count for all chapters becomes 0). Note that the chapters read on any given day must be contiguous.

- pages[n]: an array of integers representing the number of pages in each of the n chapters.
- k: an integer representing the number of consecutive chapters chosen to read on a given day.
- p: an integer representing the maximum number of pages that can be read from each chosen chapter in a day.

The function should return a long integer representing the minimum number of days needed to read all the chapters.

Example:

Let's say there are n=3 chapters with page counts pages = [3, 1, 4]. The student reads k=2 consecutive chapters each day, and can read at most p=2 pages from each of those chapters.

One way the student can read all chapters is as follows (which takes 4 days as shown in the image):

Day 1: Read chapters 1 and 2. Read 2 pages from chapter 1 (remaining: 3−2=1) and 1 page from chapter 2 (remaining: 1−1=0). Remaining pages: [1,0,4].
Day 2: Read chapters 1 and 2. Read 1 remaining page from chapter 1 (remaining: 1−1=0) and 0 pages from chapter 2 (remaining: 0−0=0). Remaining pages: [0,0,4].
Day 3: Read chapters 2 and 3. Read 0 pages from chapter 2 (remaining: 0−0=0) and 2 pages from chapter 3 (remaining: 4−2=2). Remaining pages: [0,0,2].
Day 4: Read chapters 2 and 3. Read 0 pages from chapter 2 (remaining: 0−0=0) and 2 remaining pages from chapter 3 (remaining: 2−2=0). Remaining pages: [0,0,0].
The example suggests that the chapters must be read contiguously.

Sample Case 0:

In this case, there are n=2 chapters with pages [3, 4]. Each day, the student reads k=1 chapter, and can read at most p=2 pages from it.

Let's trace this sample case:

Day 1: Choose chapter 1 (pages = 3). Read min(3,2)=2 pages. Remaining pages: [3−2,4]=[1,4].
Day 2: Choose chapter 1 (pages = 1). Read min(1,2)=1 page. Remaining pages: [1−1,4]=[0,4].
Day 3: Choose chapter 2 (pages = 4). Read min(4,2)=2 pages. Remaining pages: [0,4−2]=[0,2].
Day 4: Choose chapter 2 (pages = 2). Read min(2,2)=2 pages. Remaining pages: [0,2−2]=[0,0].
So, for this sample case, the minimum number of days would be 4.

Constraints:
1≤n≤10^5
1≤pages[i]≤10^9
1≤k≤n
1≤p≤10^9

Amazon has launched a "Play to Win" game where users get a chance to earn free gift vouchers. The game presents you with an array of integers (arr) and an integer k. You are allowed to choose any contiguous subarray within arr and add an integer x of your choice to all the elements within that subarray. You can do this at most once.

The goal is to maximize the number of elements in the entire array that have a value equal to k after performing this operation (choosing a subarray and adding x to it).

You need to complete the function getMaximumCount which takes the integer array arr and the target value k as input, and returns the maximum number of elements equal to k that can be achieved.

Example:

Given arr = [2, 3, 2, 4, 3, 2] and k = 2.

If we choose the subarray [4, 3] (from index 3 to 4) and add x = -2 to it, the array becomes [2, 3, 2, 2, 1, 2]. In this new array, there are four elements with the value 2. It's stated that this is the maximal count achievable, so the answer would be 4.

Constraints:

1≤n≤2⋅10^5 (where n is the size of the array arr)
1≤arr[i]≤2⋅10^5 (for each element in arr)
1≤k≤2⋅10^5

Sample Case 0:

Input:
Array size n=6
Array arr=[6,4,4,6,4,4]
Target value k=6
Output:

Explanation:
By choosing the subarray from index 1 to 5 (inclusive, assuming 0-based indexing, so the subarray is [4,4,6,4,4]) and adding x=2 to it, the subarray becomes [6,6,8,6,6]. The resulting array would be [6,6,6,8,6,6]. This gives us 5 elements equal to k=6, which is stated to be maximal.