- Practice
- Data Structures
- Heap
- Jesse and Cookies
- Discussions

# Jesse and Cookies

# Jesse and Cookies

- MF
max_au + 5 comments This problem is mistakenly placed into Queue subdomain, while it must be placed under 'Heap'. I wasted some time trying to understand how it's possible to effectively use a queue (and not min-heap that immediately comes to mind).

nwicakson + 2 comments hint : use priority_queue

- MF
max_au + 1 comment priority queue is NOT a queue. It's a heap.

nwicakson + 1 comment oh. then, use 2 queues. but, sort it before u push the inputs to the first queue.

dwij28 + 2 comments That makes no sense sir. This question requires a min heap priority queue which in reality is not a f-i-f-o queue.

arpadzsoltjakab + 0 comments You can solve this without a heap, only use pure Queue. You need to sort the input first, and then use two simple Queue. An init queue and an other to store the new made cookies. Every time a cookie is made, the time complexity will be constant time. The final time complexity will be O(nlogn + number of operations).

hammeramr + 0 comments a heap can be used to implement a priority que and thus they are synonymos.

A[0] remains empty A[1] is the heap head (max or min your choice) and for A[k] the left node is at A[2k] and the right at A[2k + 1]

here is my solution using a PriorityQueue

public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int operations = 0; PriorityQueue<Integer> que = new PriorityQueue<Integer>(); for(int i = 0; i < n; i++) { que.add(sc.nextInt()); } while(que.size() > 1 && que.peek() < k) { int leastSweet = que.poll(); int secondLeast = que.poll(); que.add(leastSweet + 2*secondLeast); operations++; } if(que.peek() < k) { System.out.print(-1); } else { System.out.print(operations); } } }

maximshen + 1 comment It inherits from java.util.AbstractQueue, but it is NOT queue tho

TusharDwivedi + 1 comment In C++ as well, they have kept it under , may be while deciding the container, they might have given preference ot application over implementation.

maximshen + 0 comments It could be. But it is just so confusing at the first place

charlesqwu + 0 comments So did I!

xuhuanze + 0 comments You may sovel this by using two queues.

kkvivek + 1 comment It is rightly placed under queue. I solved it using queue in O(n). Hint: Use two queue

- RW
rwan7727 + 0 comments C++ solution, passed all tests:

int main() { int n,k; cin >> n >> k; // enter values priority_queue <int,vector<int>,greater<int>> q; for (int i=0;i<n;i++) { int x; cin >> x; q.push(x); } // process int count=0; while(true){ int x; if ((x=q.top())<k) { q.pop(); // remove 1st if (q.empty()) { // nothing left, can't proceed cout << -1; break; } int y=2*q.top(); q.pop(); // remove 2nd q.push(x+y); // create new count++; // completed 1 op } else { cout << count; // print ans break; } } return 0; }

BugshotGG + 0 comments This crummy trend in Hackerrank problem description is becoming really annoying. Please provide more test cases and/or explain better the problem.

Here the "-1" case is really ambiquious and I had to take shots on what the author had in mind...

ahmetb + 2 comments Even though I'm

`heapify`

ing the array only once and using min-heap to store and operate on the data, I'm getting timeouts from cases #20, #21, #22 and #23. (large inputs)My submission is here: https://www.hackerrank.com/challenges/jesse-and-cookies/submissions/code/28210608 any ideas how I can make this faster? I could not spot any issues with my heap, my pop/push operations are O(logn).

- EJ
eric3141 + 2 comments Hi, the submission code takes about 16 seconds on my machine and profiling shows almost all the time goes to the down function. The file input23.txt has one million 1 values. I did not look at the code or debug it, but an idea is maybe what is happening is your down function should be stopping at the root because arr[0]==arr[1]==arr[2], but instead propagates identical values from the root all the way to the leaf?

elint + 0 comments Can you explain what the fact that the root has same values as his children tells you about the rest of the heap?

- S
sheridanlgrant + 0 comments I had persistent timeout from #20 similarly. You should never be computing the length of the heap--for me, this required a try/except statement in Python that finally did the trick.

benazus + 1 comment This problem is easy with a priority queue, not with a heap. I think this problem should be moved to another section or its difficulty should be increased.

- AB
aaronbannin + 0 comments I agree that this probably shouldn't be categorized as 'easy'. Heaps are the standard way to implement a priority queue. The easy approach would be to use a library, and the more challenging path is to create a heap yourself.

- CE
coleslawstl + 0 comments solution for python 3 using heapq

from heapq import heappop,heappush,heapify firstLine = [int(x) for x in input().split()] cookies = [int(x) for x in input().split()] cookieCount = int(firstLine[0]) minSweetness = int(firstLine[1]) heapify(cookies) fC = 0 try: while cookies[0] < minSweetness: fC+=1 c1 = heappop(cookies) c2 = heappop(cookies) newCookie=(1*c1)+(2*c2) heappush(cookies,newCookie) print(fC) except: print("-1")

- LT
lingbo19_tang + 0 comments You have to build the heap from strach, so I think it's meduim.

vikas_singh_MCA + 2 comments 8 90 13 47 74 12 89 74 18 38 can any one explain how it come 5 answer

- AP
AParadiso + 1 comment My code is failing on this test case as well and I do not think the answer should be 5. The mixing should be (if I understand this problem correctly) to be:

Input: 8 90 / 13 47 74 12 89 74 18 38

Output:

Mixing= 1 X 12 + 2 X 13 = 38

Mixing= 1 X 18 + 2 X 38 = 94

greater than: 90

Operations = 2

- MK
manish_1505 + 0 comments All the cookies sweetness level should be above 90.Read the question again.

NISHITA31 + 1 comment Input: 8 90 13 47 74 12 89 74 18 38

tree(heap) formed for given input: 12 13 18 38 89 74 74 47

in operation 1 deleted nos=12,13

tree: 18 38 38 47 89 74 74

in operation 2 deleted nos=18,38

tree: 38 47 74 74 89 94

in operation 3 deleted nos=38,47

tree: 74 74 89 94 132

in operation 4 deleted nos=74,74

tree: 89 94 132 222

in operation 5 deleted nos=89,94

tree: 132 222 277

Since 132>90, therefore total number of operations required=5. Hope this helps :)

vikas_singh_MCA + 0 comments thanks I get it.

- SJ
swapnilsj + 0 comments Poorely drafted question! Should provide more example cases to understand the problem.

Fiorix + 0 comments This exercise is hell if you try to use queues. Use minheap instead and it becomes the easiest problem of the day :)

Sort 115 Discussions, By:

Please Login in order to post a comment