Algorithm


Problem Name: Data Structures - Jesse and Cookies

Problem Link: https://www.hackerrank.com/challenges/jesse-and-cookies/problem?isFullScreen=true

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.

 

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;
 }
Copy The Code & Try With Live Editor

#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 & Try With Live Editor

#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);
        }
    }
}
Copy The Code & Try With Live Editor

#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);
});
Copy The Code & Try With Live Editor

#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))
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Maximum Element solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Equal Stacks solution in Hackerrank - Hacerrank solution C, C++, java,js, Python