Solving Jesse And Cookies Problem On HackerRank

In the previous post we solved a LeetCode problem that required us to find the \(k^{th}\) largest element in an unsorted array. In this post we are going to solve the Jesse and cookies problem on HackerRank.

Problem

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 \times \,\) Least sweet cookie \(+ \,2 \times \,\) 2nd least sweet cookie).

This occurs until all the cookies have a sweetness \(\geq k\).

Given the sweetness of a number of cookies, determine the minimum number of operations required until we have all cookies with sweetness \(\geq k\). If it is not possible, return \(-1\).

Solution

We are going to solve this problem using a min heap. Firstly, we add all the elements in the list to a min heap. This has time complexity of \(O(n\log(n))\). Then after that we are going to iterate through our heap. If the root’s value is less than \(k\), we pop() it and the one after it, mix them together using the formula above, and insert the new cookie back into the min heap then increment count. We keep doing this until the root has a value greater or equal to \(k\) or there’s one item left in the heap. If there’s one item left and it’s less than \(k\) we return \(-1\). Here is the code:

class Result
{

    /*
     * Complete the 'cookies' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY A
     */

    static List<int> _items;
    public static int cookies(int k, List<int> A)
    {
        _items = new List<int>();
        int count = 0;
        foreach (var item in A){
            Insert(item);
        }

        while (Peek() < k && _items.Count > 1){
            Insert(Pop() + 2 * Pop());
            count++;
        }

        if (Peek() < k){
            count = -1;
        }

        return count;
    }

    static int GetParentIndex(int i) => (i - 1) / 2;
    static int GetLeftIndex(int i) => 2 * i + 1;
    static int GetRightIndex(int i) => 2 * i + 2;

    static int Peek() => _items[0];

    static int Pop() {
        var val = _items[0];
        var i = _items.Count - 1;
        _items[0] = _items[i];
        _items.RemoveAt(i);
        BubbleDown();
        return val;
    }

    static void Insert(int val){
        _items.Add(val);
        BubbleUp();
    }

    static void BubbleUp(){
        var i = _items.Count - 1;
        while (i > 0){
            var parent = GetParentIndex(i);
            if (_items[i] < _items[parent]){
                Swap(i, parent);
                i = parent;
            }else{
                break;
            }
        }
    }

    static void BubbleDown(){
        int i = 0;
        while(true){
            var left = GetLeftIndex(i);
            var right = GetRightIndex(i);
            var min = i;
            if (left < _items.Count && _items[min] > _items[left]){
                min = left;
            }

            if (right < _items.Count && _items[min] > _items[right]){
                min = right;
            }

            if (min == i){
                break;
            }

            Swap(i, min);
            i = min;
        }

    }

    static void Swap(int x, int y){
        var temp = _items[x];
        _items[x] = _items[y];
        _items[y] = temp;
    }

}

In this post we solved the Jesse and cookies problem on HackerRank using a min heap. This is going to be the last post in the binary heap mini series. In the next post we are going to start a mini series on graphs. Please feel free to leave a question and/or suggestion. Thanks so much for reading.