# PROBLEM LINK:

Div1, Div2Practice

**Author:**Praveen Dhinwa

**Tester:**Triveni Mahatha

**Editorialist:**Adarsh Kumar

# DIFFICULTY:

Easy-Medium# PREREQUISITES:

Binary search# PROBLEM:

You are given an array A of N integers. You need to find the smallest K that satisfies this inequality; \sum \limits_{i=1}^N \left \lceil \frac{A*}{K} \right \rceil \le H, where \left \lceil \right \rceil indicates the ceil function.

# EXPLANATION:

According to the problem statement, Chef will need \left \lceil \frac{A*}{K} \right \rceil hours to finish the i^{th} pile. Hence, we need to find the smallest K that satisfies this inequality; \sum \limits_{i=1}^N \left \lceil \frac{A*}{K} \right \rceil \le H.

### Subtask #1

Iterate over values of K from 1 to MAX and break whenever you find the solution. Time complexity for the same will be O(N.MAX), where MAX is maximum element that can be present in the array.

### Subtask #2

For this subtask we need something better than brute-force. Hence, we will try to make some-observations first. Lets name the left side of our function as cost function. Observe that, our cost function is inversely proportional to K. Our cost function will decrease while K increases. At some point it will become smaller than H. We need to find this point. Observe that, this problem has reduced to standard formulation of binary search problem. We just need to binary search on values of K now and change the limits of K according to the difference between our cost function and H. For more implementation details, you can have a look at attached solutions.

# Time Complexity:

O(N.log(MAX))