1

I am trying to solve the Hackerrank problem Jesse and Cookies:

Jesse loves cookies and wants the sweetness of some cookies to be greater than value . 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 ≥ .

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 + 2 × 6 = 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 ≥ = 9 so the process stops after 4 iterations. Return 4.

I couldn't find a JavaScript solution or a hint for this problem. My code seems to be working, except that it times out for a large array (input size > 1 million).

Is there a way to make my code more efficient? I think the time complexity is between linear and O(n log n).

My Code:

function cookies(k, A) {
  A.sort((a,b)=>a-b)
  let ops = 0;
  while (A[0] < k && A.length > 1) {
    ops++;
    let calc = (A[0] * 1) + (A[1] * 2);
    A.splice(0, 2);
    let inserted = false
    if (A.length === 0) { // when the array is empty after splice
      A.push(calc);
    } else {
      for (var i = 0; i < A.length && !inserted; i++) {
        if (A[A.length - 1] < calc) {
          A.push(calc)
          inserted = true
        } else if (A[i] >= calc) {
          A.splice(i, 0, calc);
          inserted = true
        }
      }
    }
  }
  if (A[0] < k) {
    ops = -1;
  }
  return ops;
}
trincot
  • 317,000
  • 35
  • 244
  • 286
81ackCat
  • 121
  • 1
  • 11
  • Your code is O(n^2), as you have two nested linear loops. The way to improve efficiency is by using a [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)), as your title and tag suggest, but your code does not use, which should do nothing for the outer loop, but miracles for the inner one. – Amadan Dec 17 '18 at 01:42
  • You need a more efficient priority queue. See https://stackoverflow.com/questions/42919469/efficient-way-to-implement-priority-queue-in-javascript – Jim Mischel Dec 17 '18 at 17:16

2 Answers2

1

It is indeed a problem that can be solved efficiently with a heap. As JavaScript has no native heap, just implement your own.

You should also cope with inputs that are huge, but where most values are greater than k. Those should not have to be part of the heap -- it would just make heap operations unnecessarily slower. Also, when cookies are augmented, they only need to enter back into the heap when they are not yet good enough.

Special care needs to be taken when the heap ends up with just one value (less than k). In that case it needs to be checked whether any good cookies were created (and thus did not end up in the heap). If so, then with one more operation the solution has been found. But if not, it means there is no solution and -1 should be returned.

Here is an implementation in JavaScript:

/* MinHeap implementation without payload. */
const MinHeap = { 
    /* siftDown:
     * The node at the given index of the given heap is sifted down in its subtree 
     * until it does not have a child with a lesser value. 
     */
    siftDown(arr, i=0, value=arr[i]) {
        if (i >= arr.length) return;
        while (true) {
            // Choose the child with the least value
            let j = i*2+1;
            if (j+1 < arr.length && arr[j] > arr[j+1]) j++;
            // If no child has lesser value, then we've found the spot!
            if (j >= arr.length || value <= arr[j]) break;
            // Move the selected child value one level up...
            arr[i] = arr[j];
            // ...and consider the child slot for putting our sifted value
            i = j;
        }
        arr[i] = value; // Place the sifted value at the found spot
    },
    /* heapify:
     * The given array is reordered in-place so that it becomes a valid heap.
     * Elements in the given array must have a [0] property (e.g. arrays). That [0] value
     * serves as the key to establish the heap order. The rest of such an element is just payload.
     * It also returns the heap.
     */
    heapify(arr) {
        // Establish heap with an incremental, bottom-up process
        for (let i = arr.length>>1; i--; ) this.siftDown(arr, i);
        return arr;
    },
    /* pop:
     * Extracts the root of the given heap, and returns it (the subarray).
     * Returns undefined if the heap is empty
     */
    pop(arr) {
        // Pop the last leaf from the given heap, and exchange it with its root
        return this.exchange(arr, arr.pop());
    },
    /* exchange:
     * Replaces the root node of the given heap with the given node, and returns the previous root.
     * Returns the given node if the heap is empty.
     * This is similar to a call of pop and push, but is more efficient.
     */
    exchange(arr, value) {
        if (!arr.length) return value;
        // Get the root node, so to return it later
        let oldValue = arr[0];
        // Inject the replacing node using the sift-down process
        this.siftDown(arr, 0, value);
        return oldValue;
    },
    /* push:
     * Inserts the given node into the given heap. It returns the heap.
     */
    push(arr, value) {
        // First assume the insertion spot is at the very end (as a leaf)
        let i = arr.length;
        let j;
        // Then follow the path to the root, moving values down for as long as they
        // are greater than the value to be inserted
        while ((j = (i-1)>>1) >= 0 && value < arr[j]) {
            arr[i] = arr[j];
            i = j;
        }
        // Found the insertion spot
        arr[i] = value;
        return arr;
    }
};


function cookies(k, arr) {
    // Remove values that are already OK so to keep heap size minimal
    const heap = arr.filter(val => val < k);
    let greaterPresent = heap.length < arr.length; // Mark whether there is a good cookie
    MinHeap.heapify(heap);
    let result = 0;
    while (heap.length > 1) {
        const newValue = MinHeap.pop(heap) + MinHeap.pop(heap) * 2;
        // Only push result back to heap if it still is not great enough
        if (newValue < k) MinHeap.push(heap, newValue);
        else greaterPresent = true; // Otherwise just mark that we have a good cookie
        result++;
    }
    // If not good cookies were created, then return -1
    // Otherwise, if there is still 1 element in the heap, add 1
    return greaterPresent ? result + heap.length : -1;
}

// Example run
console.log(cookies(9, [2,7,3,6,4,6])); // 4
trincot
  • 317,000
  • 35
  • 244
  • 286
0

I solved it using java. You may adapt to Javascript.

This code does not require using a heap. It just work on the same array passed. Passed all tests for me.

static int cookies(int k, int[] arr) {
    /*
     * Write your code here.
     */
    Arrays.sort(arr);
    int i = 0,
        c = arr.length,
        i0 = 0,
        c0 = 0,
        op = 0;
    while( (arr[i]<k || arr[i0]<k) && (c0-i0 + c-i)>1 ) {
        int s1 = i0==c0 || arr[i]<=arr[i0] ? arr[i++] : arr[i0++], 
            s2 = i0==c0 || (i!=c && arr[i]<=arr[i0]) ? arr[i++] : arr[i0++];
        arr[c0++] = s1 + 2*s2;
        op++;
        if( i==c ) {
            i = i0;
            c = c0;
            c0 = i0;
        }
    }

    return c-i>1 || arr[i]>=k ? op : -1;
}
  • First of all sort array.
  • For newly calculated values, store them in the array[i0-c0] range, this new array does not require sorting, because it is already sorted.
  • When array[i-c] reaches(i==c: true) end, forget it, and work on arr[i0-c0].
yavuzkavus
  • 1,268
  • 11
  • 17