We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Jesse and Cookies
  2. Discussions

Jesse and Cookies

Sort by

recency

|

169 Discussions

|

  • samarthgaba27
     + 0 comments

    simple python solution

    def cookies(k, A):
    heapq.heapify(A)
    count = 0
    while True:
        c1 = heapq.heappop(A)
        if c1 >= k:
            return count
        if len(A) == 0:
            return -1
        c2 = heapq.heappop(A)
        new_cookie = c1 + 2 * c2
        heapq.heappush(A, new_cookie)
        count += 1
    return count

  • soulsliketopfan
     + 0 comments

    C# solution without PriorityQueue.

            private static int JesseAndCookies(int k, List<int> sweetness)
        {
            sweetness.Sort();

            if (sweetness[0] >= k)
                return 0;

            if (sweetness.Count >= 2 && sweetness[0] + 2 * sweetness[1] >= k)
                return 1;

            List<int> mixed = new List<int>();
            mixed.Add(sweetness[0] + 2 * sweetness[1]);

            int operations = 1, mixedIndex = 0, sweetnessIndex = 2;
            int mixedSum = 0;
            bool isThereSumGreaterThanK = false;

            // While there are elements < k remaining
            while (sweetnessIndex < sweetness.Count && mixedIndex < mixed.Count && sweetness[sweetnessIndex] < k)
            {
                // Last element of sweetness
                if (sweetnessIndex == sweetness.Count - 1)
                {
                    // Find the next two elements to apply the function to, if possible
                    if (mixedIndex >= mixed.Count) return isThereSumGreaterThanK ? operations + 1 : -1;

                    mixedSum = sweetness[sweetnessIndex] <= mixed[mixedIndex]
                                    ? sweetness[sweetnessIndex++] + 2 * mixed[mixedIndex++]
                                    : mixed[mixedIndex++] + 2 * sweetness[sweetnessIndex++];

                    if (mixedSum < k)
                    {
                        mixed.Add(mixedSum);
                    }
                    else if (!isThereSumGreaterThanK)
                    {
                        isThereSumGreaterThanK = true;
                    }
                    operations++;
                }

                else
                {
                    // Find the next two elements to apply the function to
                    if (mixed[mixedIndex] <= sweetness[sweetnessIndex])
                    {
                        mixedSum = mixed[mixedIndex++] + 2 * sweetness[sweetnessIndex++];
                    }
                    else if (mixed[mixedIndex] < sweetness[sweetnessIndex + 1])
                    {
                        mixedSum = sweetness[sweetnessIndex++] + 2 * mixed[mixedIndex++];
                    }
                    else
                    {
                        mixedSum = sweetness[sweetnessIndex] + 2 * sweetness[sweetnessIndex + 1];
                        sweetnessIndex += 2;
                    }

                    // Add it to mixed if its smaller than k
                    if (mixedSum < k)
                    {
                        mixed.Add(mixedSum);
                    }
                    // Notify that there is at least 1 element >= k
                    else if (!isThereSumGreaterThanK)
                    {
                        isThereSumGreaterThanK = true;
                    }
                    // New operation
                    operations++;
                }
            }

            // While there are elements < k im sweetness
            while (sweetnessIndex < sweetness.Count && sweetness[sweetnessIndex] < k)
            {
                // Last element of sweetness < k 
                // Find the next two elements to apply the function to, if possible
                if (sweetnessIndex == sweetness.Count - 1)
                {
                    return isThereSumGreaterThanK ? operations + 1 : -1;
                }

                // Apply the function to the next 2 consecutive elems in sweetnees
                mixedSum = sweetness[sweetnessIndex++] + 2 * sweetness[sweetnessIndex++];
                if (mixedSum < k)
                {
                    mixed.Add(mixedSum);
                }
                else if (!isThereSumGreaterThanK)
                {
                    isThereSumGreaterThanK = true;
                }
                operations++;
            }

            // While there are elements in mixed
            while (mixedIndex < mixed.Count)
            {
                // Last element of mixed
                if (mixedIndex == mixed.Count - 1)
                {
                    // Find the next two elements to apply the function to, if possible
                    if (sweetnessIndex >= sweetness.Count)
                    {
                        return isThereSumGreaterThanK ? operations + 1 : -1;
                    }
                    operations++;
                    mixedIndex++;
                }
                else
                {
                    // Apply the function to the next 2 consecutive elems in mixed
                    mixedSum = mixed[mixedIndex++] + 2 * mixed[mixedIndex++];
                    if (mixedSum < k)
                    {
                        mixed.Add(mixedSum);
                    }
                    else if (!isThereSumGreaterThanK)
                    {
                        isThereSumGreaterThanK = true;
                    }
                    operations++;
                }
            }
            return operations;
        }

    My thinking here is that it is only necessary to consider those mixed cookies whose sweetness < k for future calculations. Cookies with sweetness >= k are only necessary to consider when only 1 element < k remains alone at the end of the calculations.

  • joseespejo
     + 0 comments

    In the example given it says:

    Remove 6, 7 return 6 + 2 x 7 = 20 and A = [20, 16, 8, 7]

    If we have removed 6, 7 why is 7 back in A??

  • decon002
     + 0 comments

    It say k = 7 and : sweetness = 1 * Least sweet cookie + 2 * 2nd least sweet cookie But my array was A{3,9} correct answer was : sweetness = 3 + (2*9)

    Why?? 9 is least sweet cookie ?? It make my head hurt... So we don't need check the second value is sweetness or least sweet?

  • lynx3535
     + 0 comments

    C++ O(nlogn)

    The given parameters are meant to misguide you! my initial (not the optimal) solution was to use the given vector, sort it, erase the two elements in front, insert a new element according to the 1:2 given weight ratio. However, this is not the optimal solution:

    • the erase() method traverses the vector lineraly every time in order to erase the correct element, which is O(n) complexity.
    • the insert() requires manual search for the correct placement, which is O(n).
    • using push_back() instead of insert() requires sort() after each iteration which is O(nlogn)
    • solving the question using the vectors is correct however not optimal as it is solved in O(n^2) complexity.

    the correct and optimal method to solve this question is to use a MinHeap (aka a priority queue with a std::greater comperator).

    • creating the heap from the vector is done by make_heap() (aka Heapify) algorithm which is O(n).
    • using heap gives you direct access to the top() element which is the only relevant element in each iteration, in constant time O(1).
    • heap automatically sorts itself with swifting up/down every time a new element is pushed/poped, in O(logn).
    • considering the loop, the overall complexity of the code is O(nlogn).

    heres my version of the code:

    int cookies(int k, vector<int> A) {
    if(A.empty())
        return -1;
    
     priority_queue<int, std::vector<int>, std::greater<int> > heap(A.begin(),A.end(), std::greater<int>()); // min heap
		 
     int iterations = 0, c1, c2;
     
     while(heap.top() < k && heap.size() >= 2){
         c1 = heap.top();
         heap.pop();
         
         c2 = heap.top();
         heap.pop();
        
         heap.push(c1 + 2*c2);
         iterations++;
     }
     
     return (heap.top() < k) ? -1 : iterations;
}