See the original problem on HackerRank.
Solutions
Wait! Have you challenged yourself with this problem? If yes, click here to show the solution.
This is a typical job for a priority queue.
Basically, we maintain the least sweet cookie on top:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
priority_queue<int, deque<int>, greater<int>> cookies;
while (N--)
{
cin >> tmp;
cookies.push(tmp);
}
auto cnt = 0;
while (cookies.size()>1 && cookies.top()<K)
{
const auto c1 = cookies.top(); cookies.pop();
const auto c2 = cookies.top(); cookies.pop();
cookies.push(c1 + 2*c2);
++cnt;
}
cout << ((cookies.empty() || cookies.top()<K) ? -1 : cnt);
|
In python we can use the heapq module which implements a priority queue.
Please note that we leverage exceptions to do error handling:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import heapq
def cookies(k, heap):
heapq.heapify(heap)
ops = 0
while heap[0] < k:
c = heapq.heappop(heap) + 2 * heapq.heappop(heap)
heapq.heappush(heap, c)
ops += 1
return ops
try:
result = cookies(k, my_cookies_list)
except IndexError:
result = -1
print(result)
|