Jesse and Cookies

  • + 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'
    }