Discussion on Jesse and Cookies Challenge

nwicakson 4 years ago+ 2 comments

hint : use priority_queue

max_au 4 years ago+ 1 comment

priority queue is NOT a queue. It's a heap.

nwicakson 4 years ago+ 1 comment

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

dwij28 3 years ago+ 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 3 years ago+ 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 2 years ago+ 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);
        }
        
    }
}