In this HackerRank Jesse and Cookies problem, we have given n strings of brackets, we need to determine whether each sequence of brackets is balanced. if the string is balanced, return YES. otherwise, return NO.
Problem solution in 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))Problem solution in 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<Integer>(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);
}
}
}Problem solution in 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<int>, 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;
}Problem solution in 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;
}Problem solution in 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);
});
0 Comments