Jesse and Cookies

See the original problem on HackerRank.

Solutions

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)
We've worked on this challenge in these gyms: modena  padua  milan  barcelona  turin 
comments powered by Disqus