# Sugar Rush - EDITORIAL:

* Author:* kishen1912000, alphatron99

* Editorialist:* kishen1912000

# DIFFICULTY:

EASY

# PREREQUISITES:

Binary Search

# PROBLEM:

Given N piles of chocolates with C_i chocolates in the i^{th} pile, and in a turn you can pick a pile and eat at most K chocolates from it. Find the minimum K such that you can eat all chocolates in at most D turns.

# QUICK EXPLANATION:

Do a binary search on [1, max(C_i)] for K.

# EXPLANATION:

As we can observe, the value of K will be in the range [1, max(C_i)]. So, we need to find the minimum K which can clear all the chocolates in at most D turns. Time taken to check if a value of K is valid, that is you can eat all chocolates, is O(N). By implementing binary search to find the value of K, we can solve this in O(NlogN) time. Also, note if D \lt N, then it is not possible to find a K.

Now, the main aim was to reduce the source code size. In python, there is a module called bisect which can be used to solve binary search problems. Check out the setterâ€™s solution below which uses bisect_left to find the optimal K. This solution uses 297 characters. Feel free to share your approach, if it differs. Suggestions are always welcomed.

# SOLUTIONS:

## Setter's Solution

```
from bisect import bisect_left as b
import math
class t(dict):
def __missing__(self,k):
global f;return f(k)
def f(k):
global A,d
s=0
for i in A:
s+=math.ceil(i/k)
return 1 if s<=d else 0
w=t()
i=lambda: [int(j)for j in input().split()]
n,d=i()
A=i()
print(-1 if d<n else b(w,1,1,max(A)))
```