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[i]}{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[i]}{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[i]}{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.
@philomath_mht the ans. will be 8 as you can only divide maximum (7-5)=2 bunch of bananas and the minimum required bananas that should be eaten is 8.
9/8 + 3/8 + 8/8 + 10/8 + 5/8 = 2 + 1 + 1 + 2 + 1 = 7
Is there any list of other test cases beyond what is posted in the hints section. I’m matching all those 100%, and have come up with a few test cases of 100+ number and 10000+ hours and my solution seems okay to me, but I fail every test on submission.
I’m sure I’m just missing something dumb, but can’t figure it out.