## Algorithm

Problem Name: Data Structures - Jesse and Cookies

In this HackerRank in Data Structures - Jesse and Cookies solutions

Jesse loves cookies and wants the sweetness of some cookies to be greater than value k. To do this, two cookies with the least sweetness are repeatedly mixed. This creates a special combined cookie with: sweetness = (1 * Least sweet cookie + 2 * 2nd least sweet cookie). This occurs until all the cookies have a sweetness >= k.

Given the sweetness of a number of cookies, determine the minimum number of operations required. If it is not possible, return -1.

Example

k= 9

A = [2,7,3,6,4,6]

The smallest values are 2,3.

Remove them then return 2 + 2 * 3 = 8 to the array. Now

A = [8,7,6,4,6]

Remove 4,6 and return 4 + 6 * 2 =16 to the array. Now

A = [16,8,7,6]

Remove 6,7, return 6 + 2 *7 = 20 and A = [20,16,8,7]

Finally, remove 8,7 and return 7 + 2 * 8 = 23 to A. Now

A = [ 23,20,16].

All values are >= k = 9 so the process stops after 4 iterations. Return 4

Function Description
Complete the cookies function in the editor below.

• int k: the threshold value
• int A[n]: an array of sweetness values

Returns

• int: the number of iterations required or -1

Input Format

The first line has two space-separated integers, n and k, the size of A[]

and the minimum required sweetness respectively.

The next line contains n space-separated integers, A[i].

Constraints

1 <= n <= 10**6

0 <= k <= 10**9

0 <= A[i] <= 10**6

Sample Input

```STDIN               Function
-----               --------
6 7                 A[] size n = 6, k = 7
1 2 3 9 10 12       A = [1, 2, 3, 9, 10, 12]
```

Sample Output

``````2
``````

Explanation

Combine the first two cookies to create a cookie with sweetness = 1* 1 + 2 * 2 = 5

After this operation, the cookies are 3,5,9,10,12

Then, combine the cookies with sweetness 3 and sweetness 5, to create a cookie with resulting sweetness = 1 * 3 + 2 * 5 = 13

All the cookies have a sweetness >= 7

Thus, 2 operations are required to increase the sweetness.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

/* Global Variables*/
int *heap_array = NULL;
int heap_max_size = 0;
int heap_current_size = 0;

#define SIZE_OF_BLOCK_ALLOCATION  1000

void heap_heapify_from_top (int counter) {
int temp_val = 0;
int child_counter;
int has_left_child = 0;
int has_right_child = 0;

if ((2 * counter + 1)  <  heap_current_size)
has_left_child = 1;

if ((2 * counter + 2) < heap_current_size)
has_right_child = 1;

/* Now, let us find the lowest of the two children */
if (has_left_child && has_right_child) {
if (heap_array[2* counter + 1]  <  heap_array[2*counter + 2])
child_counter = 2 * counter + 1;
else
child_counter = 2 * counter + 2;
} else if (has_left_child) {
child_counter = 2 * counter + 1;
} else if (has_right_child) {
child_counter = 2 * counter + 2;
} else {
return;
}

if (heap_array[counter] > heap_array[child_counter]) {
temp_val = heap_array[counter];
heap_array[counter] = heap_array[child_counter];
heap_array[child_counter] = temp_val;
heap_heapify_from_top(child_counter);
}
return;
}

int heap_extract () {
int t = 0;
if (heap_current_size == 0) {
printf("The heap is empty\n");
return -1;
}

t = heap_array[0];
heap_array[0] = heap_array[heap_current_size-1];
heap_current_size--;

if (heap_current_size != 1) {
heap_heapify_from_top(0);
}
return t;
}

void heap_insert_heapify_from_bottom (int counter) {
int parent = (int) floor((double)(counter-1)/2);
int temp_val;

if (counter == 0) {
return;
}

if (heap_array[parent] > heap_array[counter]) {
temp_val = heap_array[counter];
heap_array[counter] = heap_array[parent];
heap_array[parent] = temp_val;
}

heap_insert_heapify_from_bottom(parent);
}

if (heap_current_size == heap_max_size) {
heap_max_size += SIZE_OF_BLOCK_ALLOCATION;
heap_array = (void*)realloc(heap_array,
heap_max_size * sizeof(int));
if (!heap_array) {
printf("realloc failed\n");
return -1;
}
}
heap_array[heap_current_size] = value;
heap_insert_heapify_from_bottom(heap_current_size);
heap_current_size++;
return 0;
}

int main (int argc, char *argv[]) {
int n, k, i, temp=0, temp2=0, num_oper=0, temp_k;
bool no_entry_with_max = true;

scanf("%d %d", &n, &k);
for (i = 0; i  < n; i++) {
scanf("%d", &temp);
}

temp = heap_extract();
if (temp >= k) {
printf("0\n");
return 0;
}
while (temp  <  k && heap_current_size) {
temp2 = heap_extract();
temp_k = temp + 2 * temp2;
num_oper += 1;
if (temp_k >= k) {
no_entry_with_max = false;
}
temp = heap_extract();
}
if (no_entry_with_max == true) {
printf("-1\n");
} else {
printf("%d\n", num_oper);
}
return 0;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N, K, ai;
priority_queue<int, vector<nt>, greater<int>> A;
cin >> N >> K;
for (int i = 0; i  <  N; ++i) {
cin >> ai;
A.push(ai);
}
int count = 0;
while (A.top()  <  K) {
if (A.size() < 2) {
cout << "-1\n";
return 0;
}
int m1 = A.top();
A.pop();
int m2 = A.top();
A.pop();
A.push(m1 + 2 * m2);
count++;
}
cout << count << endl;
return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int minSweetness = sc.nextInt();
int count = 0;
PriorityQueue < Integer> he = new PriorityQueue(numCookies);
for(int i = 0; i  <  numCookies; i++){
int sweetness = sc.nextInt();
}
while(he.peek()  <  minSweetness && he.size() > 1){
int ne = he.poll() + 2*he.poll();
count++;
}
if(he.peek() >= minSweetness){
System.out.println(count);
} else{
System.out.println(-1);
}
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
reachMinSweatness = (arr, target) => {
const minHeap = new Heap();
let count = 0;

while (minHeap.min()  <  target) {
if (minHeap.length() === 1) return -1;
const firstMin = minHeap.extractMin();
const secondMin = minHeap.extractMin();
const combinedMins = firstMin * 1 + secondMin * 2;
count += 1;
}

return count;
}

class Heap {
constructor() {
this.store = [];
}

length() {
return this.store.length;
}

min() {
return this.store[0];
}

this.store.push(el);
this.heapifyUp();
}

extractMin() {
const min = this.store[0];
this.store[0] = this.store[this.store.length - 1];
this.store.pop();
this.heapifyDown();
return min;
}

heapifyUp() {
let currentElIdx = this.store.length - 1;
let parentIdx = Math.floor((currentElIdx - 1) / 2);

while (parentIdx >= 0 && this.store[currentElIdx]  <  this.store[parentIdx]) {
const hold = this.store[currentElIdx];
this.store[currentElIdx] = this.store[parentIdx];
this.store[parentIdx] = hold;

currentElIdx = parentIdx;
parentIdx = Math.floor((currentElIdx - 1) / 2);
}

return this.store;
}

heapifyDown() {
let parentIdx = 0;
let childIndices = this.getChildIndices(parentIdx);

while (childIndices.length > 0
&& this.store[childIndices[0]]  <  this.store[parentIdx]
|| (childIndices[1] && this.store[childIndices[1]] < this.store[parentIdx])) {

if (childIndices[1] && this.store[childIndices[1]] < this.store[childIndices[0]]) {
const hold = this.store[childIndices[1]];
this.store[childIndices[1]] = this.store[parentIdx];
this.store[parentIdx] = hold;

parentIdx = childIndices[1];
childIndices = this.getChildIndices(parentIdx);
} else {
const hold = this.store[childIndices[0]];
this.store[childIndices[0]] = this.store[parentIdx];
this.store[parentIdx] = hold;

parentIdx = childIndices[0];
childIndices = this.getChildIndices(parentIdx);
}
}

return this.store;
}

getChildIndices(parentIdx) {
const childIndices = [];
if ((parentIdx * 2 + 1)  <  this.store.length) childIndices.push(parentIdx * 2 + 1);
if ((parentIdx * 2 + 2) < this.store.length) childIndices.push(parentIdx * 2 + 2);
return childIndices
}
}

function processData(input) {
const [n, target] = metaData.split(' ');
const arr = data.split(' ').map(el => parseInt(el));
const h = new Heap();
//console.log(h.extractMin(), h.store)
console.log(reachMinSweatness(arr, target));
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
from heapq import heapify, heappush, heappop

count = 0