# Ayush and Ninja Test

Posted: 18 Jan, 2021

Difficulty: Moderate

#### Ayush is studying for ninjatest which will be held after 'N' days, And to score good marks he has to study 'M' chapters and the ith chapter requires TIME[i] seconds to study. The day in Ayush’s world has 100^100 seconds. There are some rules that are followed by Ayush while studying.

#### 1. He reads the chapter in a sequential order, i.e. he studies i+1th chapter only after he studies ith chapter.

#### 2. If he starts some chapter on a particular day he completes it that day itself.

#### 3. He wants to distribute his workload over 'N' days, so he wants to minimize the maximum amount of time he studies in a day.

#### Your task is to find out the minimal value of the maximum amount of time for which Ayush studies in a day, in order to complete all the 'M' chapters in no more than 'N' days.

#### For example

```
if Ayush want to study 6 chapters in 3 days and the time that each chapter requires is as follows:
Chapter 1 = 30
Chapter 2 = 20
Chapter 3 = 10
Chapter 4 = 40
Chapter 5 = 5
Chapter 6 = 45
Then he will study the chapters in the following order
| day 1 : 1 , 2 | day 2 : 3 , 4 | day 3 : 5 , 6 |
Here we can see that he study chapters in sequential order and the maximum time to study on a day is 50, which is the minimum possible in this case.
```

##### Input Format:

```
The first line of the input contains a single positive integer 'T', denoting the number of test cases.
The first line of each test case contains two space-separated positive integers 'N' and 'M', denoting the number of days he can study before the ninja test and the number of chapters he has to study for the ninja test respectively.
The second line of each test case contains 'M' space-separated positive integers, where the ith integer denotes the time required to study the ith chapter.
```

##### Output Format:

```
For each test case print a single line containing a single integer denoting the maximum time Ayush studies in a day.
The output of each test case will be printed in a separate line.
```

##### Note:

```
You don't have to print anything, it has already been taken care of. Just Implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N , M <= 10 ^ 4
1 <= TIME[i] <= 10 ^ 9
It is considered that there are infinite seconds in a day, on the planet where Ayush lives.
Time limit: 1 sec.
```

Approach 1

- The answer could be between maximum of all available time and the sum of the time required to study all chapters. So in this solution we have all the possible answers and let’s say we are at X so we want to find whether X can be the maximum time of a day Ayush studies or not.
- We also want to allocate chapters sequentially so we will keep track of the chapters using
**currentChapter**variable which would be initialized with 1 as we are on the first chapter at the beginning. - Now we will iterate through all the days and try to allocate as many chapters in a day as possible with the total time required to study them as less than or equal to X.
- If we can cover all the chapters in N days using the above rule then we will say that it is possible for X to be the answer we will return X because it would also be the minimum possible

Approach 2

- We know that our answer could be between maximum of all available time and the sum of time required to study all the chapters. Now we will use binary search to find the answer. We will set 1 as the minimum possible answer and sum as the maximum possible answer.
- Now we will find for some X equal to the mid value of maximum and minimum possible answer.
- Let's find out whether X is a possible answer or not or we can say whether there is sum allocation where X is the maximum possible time of a day.
- We want to allocate chapters sequentially so we will keep track of the chapters using
**currentChapter**variable which would be initialized with 1 as we are on the first chapter at the beginning. - Now we will iterate through all the days and try to allocate as many chapters in a day as possible with the total time required to study them as less than or equal to X.
- If we can cover all the chapters in N days using the above rule then we will say that it is possible for X to be the answer.

- We want to allocate chapters sequentially so we will keep track of the chapters using
- If X is a possible answer then we will compress our range to the right hand side i.e, we will search on X - max possible answer.
- If X is not possible answer then we will compress our range to the left hand side i.e, we will search on min possible answer - X.
- By doing this or range becomes smaller and smaller and when it becomes equal to 1 we will return that as an answer.

SIMILAR PROBLEMS

# Two Sum II - Input Array Is Sorted

Posted: 4 Mar, 2022

Difficulty: Moderate

# Ninja And Matrix

Posted: 12 Apr, 2022

Difficulty: Easy

# Ninja In Interview

Posted: 13 Apr, 2022

Difficulty: Easy

# Missing Number

Posted: 17 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate