Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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.
cookies has the following parameters:
- 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
Now, the cookies are 9.10.12,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);
}
int heap_add (int value) {
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);
heap_add(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;
heap_add(temp_k);
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;
}
#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;
}
#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 numCookies = sc.nextInt();
int minSweetness = sc.nextInt();
int count = 0;
PriorityQueue < Integer> he = new PriorityQueue(numCookies);
for(int i = 0; i < numCookies; i++){
int sweetness = sc.nextInt();
he.add(sweetness);
}
while(he.peek() < minSweetness && he.size() > 1){
int ne = he.poll() + 2*he.poll();
he.add(ne);
count++;
}
if(he.peek() >= minSweetness){
System.out.println(count);
} else{
System.out.println(-1);
}
}
}
#4 Code Example with Javascript Programming
Code -
Javascript Programming
reachMinSweatness = (arr, target) => {
const minHeap = new Heap();
arr.forEach(el => minHeap.add(el));
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;
minHeap.add(combinedMins);
count += 1;
}
return count;
}
class Heap {
constructor() {
this.store = [];
}
length() {
return this.store.length;
}
min() {
return this.store[0];
}
add(el) {
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 [metaData, data] = input.split('\n');
const [n, target] = metaData.split(' ');
const arr = data.split(' ').map(el => parseInt(el));
const h = new Heap();
//arr.forEach(el => h.add(el));
//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);
});
#5 Code Example with Python Programming
Code -
Python Programming
from heapq import heapify, heappush, heappop
def get_number_mixes(cookies, minimum_value):
cookies = list(cookies)
heapify(cookies)
count = 0
while cookies[0] < minimum_value:
if len(cookies) < 2:
return -1
heappush(cookies, heappop(cookies) + 2 * heappop(cookies))
count += 1
return count
N, K = map(int, input().split())
A = map(int, input().split())
print(get_number_mixes(A, K))