We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Heap
  4. Jesse and Cookies
  5. Discussions

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

      • JimB6800 + 1 comment

        It's impossible to solve this in O(n). You sorted the input - that's O(n log n).

        • h_roark + 0 comments

          You can sort in O(N) using Count Sort, the numbers in the array are < 10^6

    • 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;
}