Jesse and Cookies

Sort by

recency

|

176 Discussions

|

  • + 0 comments
       priority_queue<int ,  vector<int>  , greater<int>> pq;
        for(int i = 0 ; i <A.size() ;i++)
        {  
            pq.push(A[i]);   
        }
        
        int ct =0;
        
        while (!pq.empty()) {
            
            if(pq.top() >= k)
            {
                break;
            }
            
            if(pq.size() <2)
            {
                ct = -1;
                break;
            }
            
            int first = pq.top();
            pq.pop();
            int second = pq.top();
            pq.pop();
            
            int sweetness =  first  + (2 * second);    
            pq.push(sweetness);
            ct++;
        }
        
        return ct;``
    
  • + 0 comments

    Python:

    def cookies(k: int, A: list) -> int:
        heapq.heapify(A)
        counter = 0         # no. of operations
        while A[0] < k:     # smallest element always first
            if len(A) < 2:
                return -1
            first = heapq.heappop(A) 
            second = heapq.heappop(A) 
            heapq.heappush(A, first + 2 * second)
            counter += 1
        return counter
    
  • + 0 comments

    Fairly confident the size of remaining cookies' sweetness should reduce by 1 every time a calculation is completed; however the example shows a step where that does not happen.

  • + 0 comments

    My answer with Typescript.

    Firsts of all, i tried using loop and sequential search/sort to find the 2 smallest elements, it worked but not fast enough.

    function cookies(k: number, A: number[]): number {
        A.sort((a, b) => a - b);
    
        let iterations = 0;
        while (A[0] < k) {
            if (A.length < 2) return -1;
    
            const l1 = A.shift()!;
            const l2 = A.shift()!;
            const newCookie = l1 + 2 * l2;
    
            let low = 0, high = A.length;
            while (low < high) {
                const mid = Math.floor((low + high) / 2);
                if (A[mid] < newCookie) low = mid + 1;
                else high = mid;
            }
            A.splice(low, 0, newCookie);
    
            iterations++;
        }
    
        return iterations;
    }
    

    Then i tried using MinHeap and it was surprisingly fast, all tests completed instantly

    class MinHeap {
        private heap: number[] = [];
    
        insert(value: number): void {
            this.heap.push(value);
            this.heapifyUp();
        }
    
        extractMin(): number | undefined {
            if (this.heap.length === 1) return this.heap.pop();
            const min = this.heap[0];
            this.heap[0] = this.heap.pop()!;
            this.heapifyDown();
            return min;
        }
    
        peek(): number | undefined {
            return this.heap[0];
        }
    
        size(): number {
            return this.heap.length;
        }
    
        private heapifyUp(): void {
            let index = this.heap.length - 1;
            while (index > 0) {
                const parentIndex = Math.floor((index - 1) / 2);
                if (this.heap[index] >= this.heap[parentIndex]) break;
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            }
        }
    
        private heapifyDown(): void {
            let index = 0;
            while (index * 2 + 1 < this.heap.length) {
                let minChildIndex = index * 2 + 1;
                if (index * 2 + 2 < this.heap.length && this.heap[index * 2 + 2] < this.heap[minChildIndex]) {
                    minChildIndex = index * 2 + 2;
                }
                if (this.heap[index] <= this.heap[minChildIndex]) break;
                [this.heap[index], this.heap[minChildIndex]] = [this.heap[minChildIndex], this.heap[index]];
                index = minChildIndex;
            }
        }
    }
    
    function cookies(k: number, A: number[]): number {
        const heap = new MinHeap();
        A.forEach(num => heap.insert(num));
    
        let iterations = 0;
    
        while (heap.peek()! < k) {
            if (heap.size() < 2) return -1;
            const l1 = heap.extractMin()!;
            const l2 = heap.extractMin()!;
            heap.insert(l1 + 2 * l2);
            iterations++;
        }
    
        return iterations;
    }
    
  • + 0 comments

    JavaScript Solution :-

    class MinHeap {
        constructor() {
            this.heap = [];
        }
    
        push(val) {
            this.heap.push(val);
            this.bobbleUp();
        }
    
        pop() {
            if (this.size() === 1) return this.heap.pop();
            const top = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.bobbleDown();
            return top;
        }
    
        peek() {
            return this.heap[0];
        }
    
        size() {
            return this.heap.length;
        }
    
        bobbleUp() {
            let index = this.heap.length - 1;
            while (index > 0) {
                const presentIndex = Math.floor((index - 1) / 2);
                if (this.heap[index] >= this.heap[presentIndex]) break;
                [this.heap[index], this.heap[presentIndex]] = [this.heap[presentIndex], this.heap[index]];
                index = presentIndex;
            }
        }
    
        bobbleDown() {
            let index = 0;
            const length = this.heap.length;  // Fixed typo: 'lenght' -> 'length'
            const element = this.heap[0];
            while (true) {
                let leftChildIndex = 2 * index + 1;
                let rightChildIndex = 2 * index + 2;
                let swap = null;
    
                if (leftChildIndex < length) {
                    if (this.heap[leftChildIndex] < element) {
                        swap = leftChildIndex;
                    }
                }
    
                if (rightChildIndex < length) {
                    if (
                        (swap === null && this.heap[rightChildIndex] < element) ||
                        (swap !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
                    ) {
                        swap = rightChildIndex;
                    }
                }
    
                if (swap === null) break;
                [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
                index = swap;
            }
        }
    }
    
    function cookies(k, A) {
        const heap = new MinHeap();
        for (const sweetness of A) {
            heap.push(sweetness);
        }
    
        let oprs = 0;
        while (heap.size() > 1 && heap.peek() < k) {
            const leastSweet = heap.pop();
            const secondLeastSweet = heap.pop();
            const newSweetness = leastSweet + 2 * secondLeastSweet;
            heap.push(newSweetness);
            oprs++;
        }
    
        return heap.peek() >= k ? oprs : -1;  // Fixed 'heep' -> 'heap'
    }