# Hacker rank Jesse and Cookies

I am trying to solve a problem on Hacker Rank and the question is as follows:

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value $K$. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with:

sweetness =(1× Least sweet cookie + 2× 2nd least sweet cookie).


He repeats this procedure until all the cookies in his collection have a sweetness $\ge K$. You are given Jesse's cookies. Print the number of operations required to give the cookies a sweetness $\ge K$. Print $−1$ if this isn't possible.

## Input Format

The first line consists of integers $N$, the number of cookies and $K$, the minimum required sweetness, separated by a space. The next line contains $N$ integers describing the array $A$ where $Ai$ is the sweetness of the $i$th cookie in Jesse's collection.

## Constraints

$1\le N\le 10^6$
$0\le K\le 10^9$
$0\le Ai\le 10^6$

## Output Format

Output the number of operations that are needed to increase the cookie's sweetness $\ge k$. Output $−1$ if this isn't possible.

For this I have written code in Java like this:

    public class Solution {
Collections.sort(newList);
int count=0;
while(newList.getFirst()<k){
if(newList.size()>=2){
count++;
int tempFirst = newList.removeFirst();
int tempSecond = newList.removeFirst();
Collections.sort(newList);
}
else{
return -1;
}
}
return count;
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Solution newObj = new Solution();
Scanner scanObj = new Scanner(System.in);
long minSweetness = scanObj.nextLong();
}
System.out.println(newObj.getMinStepsToGetK(minSweetness,newList));
}
}


For the above code I am getting half of my test cases right and the other half is giving time out exception (taking more than 4 seconds to give output). My question is basically: where can I improve the performance of the code? Is there any other approach which I should go about?

• Not really a big fan of cookies, btw. Commented Feb 3, 2016 at 23:06
• You may check: stackoverflow.com/a/57317912/1856618 Commented Aug 1, 2019 at 22:54

Your algorithm can be summarized as follows:

1. Fetch the list of cookies and sort in ascending order.
2. Initialize a counter to zero
3. If the smallest cookie is less than K, then:
• (a) Increment the counter and combine this cookie with the next smallest cookie (or return -1 if there are fewer than 2 cookies left)
• (b) Remove the two smallest cookies from the list and add the new cookie to the list
• (c) Sort the list in ascending order again
4. Otherwise, exit with the value of the counter
5. Go back to step 3

Your code is taking a long time to run because you are sorting the entire list at step 3(c). This is unnecessary; since the list is already sorted (apart from the new value being added), you can just do a binary search in $\mathcal{O}(\log(n))$ time to find the correct position in which to insert the combined cookie. This is going to be much faster than sorting, which typically takes $\mathcal{O}(n\log(n))$ time.

An even better approach would be to use a min-heap data structure, which will keep track of the smallest element in a set in the most efficient way possible.

I converted your code to use a PriorityQueue data structure (Java's equivalent to a min-heap). I also created some test data using the following code:

perl -e '$n=100000;$h=$n/2;print "$n $h\n";for$i(0..$n){$r = int(rand()*$n); print "$r ";};print "\n";' > testdata.txt


Your original code took 1 minute to process 100,000 items. With a priority queue, this went down to 0.7 seconds. Here's my code:

import java.util.*;

public class Solution2 {

private static int getMinStepsToGetK(long k,PriorityQueue<Integer> newQueue){
int count=0;
while(newQueue.peek()<k) {
if(newQueue.size()>=2) {
count++;
int tempFirst = newQueue.poll();
int tempSecond = newQueue.poll();
newQueue.offer(tempFirst+(tempSecond*2));
}
else {
return -1;
}
}
return count;
}

public static void main(String[] args) {
Scanner scanObj = new Scanner(System.in);
long minSweetness = scanObj.nextLong();
PriorityQueue<Integer> newQueue = new PriorityQueue<Integer>();

Note: There's no need to create a new Solution object in order to access the getMinStepsToGetK() member function. Since it isn't needed externally, I declared it as a private static function.