Sort by

recency

|

358 Discussions

|

  • + 0 comments
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
    
        public static void main(String[] args) {
        
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int k=scan.nextInt();
            PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
            for(int i=0;i<n;i++)
                {
                queue.add(scan.nextInt());
            }
            int count=0;
            while(queue.peek()<k)
                {
                if(queue.size()>=2)
                    {
                int x=queue.remove();
                int y=queue.remove();
                y=x+2*y;
                queue.add(y);
                count++;
                }
                else
                    {
                    count=-1;
                    break;
                }
            }
            System.out.println(count);
        }
    }
    
  • + 0 comments
    int cookies(int k, vector<int> arr) {
        priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.end());
        int count = 0;
    
        while (pq.size() > 1 && pq.top() < k)
        {
            int first = pq.top();
            pq.pop();
            int second = pq.top();
            pq.pop();
    
            pq.push(first + 2 * second);
            count++;
        }
        return (pq.top() >= k) ? count : -1;   
    }
    
  • + 1 comment

    Here is my solution. It uses python heapq library. It is fast

    def cookies(k, A):
        import heapq
    
        heapq.heapify(A)
        count = 0
        while not all(i >= k for i in A): # until all cookies are >= k
            if len(A) == 1:
                return -1
            a, b = heapq.heappop(A), heapq.heappop(A)
            c = a + 2 * b
            heapq.heappush(A, c)
            count += 1
        return count
    
    • + 0 comments

      do you knwo what is the difference between your code and: for some reason having if A[0] >= k: inside while loop makes case 18 fail def cookies(k, A): # Write your code here heapq.heapify(A) count = 0 while len(A) >= 2: if A[0] >= k: return count x = heapq.heappop(A) y = heapq.heappop(A) heapq.heappush(A, x+(2*y)) count += 1 return -1

  • + 0 comments

    JAVA Using PriorityQueue

    class Result {
        public static int cookies(int k, List<Integer> A) {
            if (A.size() == 0) return -1;
            if (A.size() == 1) {
                return (A.get(0) < k) ? -1 : 0;
            }
            Queue<Integer> heap = new PriorityQueue<>(A);
            int steps = 0;
            while(heap.peek() < k){
                if(heap.size() < 2) return -1;
                int c1 = heap.poll();
                int c2 = heap.poll();
                heap.add(c1 + (c2 * 2));
                steps += 1;
            }
            return steps;
        }
    }
    
  • + 0 comments

    Guys, I implemented the whole MinHeap and stuff:

    class MinHeap:
        def __init__(self, arr=[]):
            self.heap = arr[:]
            self.convert_to_heap()
    
        def heapify_up(self, index):
            parent = (index - 1) // 2
            while index > 0 and self.heap[index] < self.heap[parent]:            
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]            
                index = parent
                parent = (index - 1) // 2
    
        def heapify_down(self, index):
            l = len(self.heap)
            while True:
                current = index
                left = (2 * index) + 1
                right = (2 * index) + 2
    
                # Check that left and right indexes are lesser than the heap's size and, therefore, are able to access its elements. Else, an index out of range error will be thrown.
                if left < l and self.heap[left] < self.heap[current]:
                    current = left
                if right < l and self.heap[right] < self.heap[current]:
                    current = right
                # In case that any value computed for the left or right indexes, which correspond to the indexes of current's children, is greater than the heap's size:
                # * It means that current's value, which hwas updated in the prior iteration, corresponds to a leaft
                # * Index's value will not be updated and, therefore, will equal current's value, which was set in the prior iteration.
                if current == index:
                    break
    
                self.heap[index], self.heap[current] = self.heap[current], self.heap[index]
                index = current
    
        def convert_to_heap(self):
            for i in range((len(self.heap) // 2 ) - 1, -1, -1):
                self.heapify_down(i)
    
        def insert(self, val):
            self.heap.append(val)
            self.heapify_up(len(self.heap) - 1)
    
        def pop_root(self):
            if not self.heap:
                return None
            root = self.heap[0]
            last = self.heap.pop()
            if self.heap:
                self.heap[0] = last
                self.heapify_down(0)
            return root
        
        def delete_value(self, val):
            if val not in self.heap:
                return
            
            index = self.heap.index(val)
            last = self.heap.pop()
    
            if index < len(self.heap):
                self.heap[index] = last
                if index > 0 and self.heap[index] < self.heap[(index - 1) // 2]:
                    self.heapify_up(index)
                else:
                    self.heapify_down(index)
    
        def get_root(self):
            return self.heap[0]
    
    def cookies(k, A):
        heap = MinHeap(A)
        count = 0
        
        print(f"h = {heap.heap}")
        while len(heap.heap) > 1 and heap.get_root() < k:
            flsc = heap.pop_root()
            slsc = heap.pop_root()
            print(f"r1 = {flsc}, r1 = {slsc}")
    
            if slsc is None:  # Si no hay una segunda galleta, no se puede continuar
                return -1
    
            new_cookie = flsc + (2 * slsc)
            heap.insert(new_cookie)
            count += 1
            print(f"heap = {heap.heap}")
    
        return count if heap.get_root() is not None and heap.get_root() >= k else -1
    

    However, test case 22 was throwing a TLE, so I cahnged the whole code for this instead:

    import heapq
    
    def cookies(k, A):
        heapq.heapify(A)
        count = 0
        
        print(f"h = {heap.heap}")
        while len(A) > 1 and A[0] < k:
            flsc = heapq.heappop(A)
            slsc = heapq.heappop(A)
    
            heapq.heappush(A, flsc + (2 * slsc))
            count += 1
    
        return count if A[0] >= k else -1