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

# Jesse and Cookies

# Jesse and Cookies

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

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 + 1 comment 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); } } }

pc06matt + 0 comments My solution is exactly like this, but 2 cases are failing because of timeout. How did you resolve it?

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.

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...

aashray14 + 1 comment Getting testcase 18 as wrong . Can't figure out what edge case I'm missing

sund3r + 2 comments Me too.

EDIT: Figured it out. For me, it was the case where there is one element in the heap, and it happens to be >= K.

khusrav + 0 comments Thank you, helped me!

vikisquarez + 0 comments Thank you it helped

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).

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?

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 + 2 comments 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.

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.

pc06matt + 0 comments I agree this should be under 'EASY' category.

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")

lingbo19_tang + 1 comment You have to build the heap from strach, so I think it's meduim.

karlf_89 + 1 comment you only need to build the heap from scratch if you are using a language like C. Java, C++, C#, python have a heap structure that you can use.

devansh1497 + 0 comments You have the PriorityQueue class in Java also. I don't use C++ alot but I am sure that it also has priority queue library.

IanAMcLaughlin + 0 comments my java solution:

static int cookies(int k, int[] A) { PriorityQueue<Integer> pq = new PriorityQueue<>(); int operations = 0; //Initialize priority queue for(int a : A) { pq.add(a); } while(pq.size() > 1) { if(pq.peek() >= k) { return operations; } else { int cookie1 = pq.poll(); int cookie2 = pq.poll(); int newCookie = cookie1 + cookie2 * 2; pq.add(newCookie); operations++; } } if(pq.size() > 0 && pq.peek() >= k) { return operations; } else { return -1; } }

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

kyxap + 0 comments Done it in Java8 but randomly failed tests 20,21,23 due to timeout. After 3d of 4d submittion all passed :) FYI

Sort 153 Discussions, By:

Please Login in order to post a comment