Jesse and Cookies

  • + 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.