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 {
public int getMinStepsToGetK(long k,LinkedList newList){
Collections.sort(newList);
int count=0;
while(newList.getFirst()=2){
count++;
int tempFirst = newList.removeFirst();
int tempSecond = newList.removeFirst();
newList.add(tempFirst+(tempSecond*2));
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 So

Your algorithm can be summarized as follows:

• Fetch the list of cookies and sort in ascending order.

• Initialize a counter to zero

• 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

• Otherwise, exit with the value of the counter

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

Addendum:

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 newQueue){
    int count=0;
    while(newQueue.peek()=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);
    int numOfCookies = scanObj.nextInt();
    long minSweetness = scanObj.nextLong();
    PriorityQueue newQueue = new PriorityQueue();
    for(int i=0;i<numOfCookies;i++) {
      newQueue.offer(scanObj.nextInt());
    }
    System.out.println(getMinStepsToGetK(minSweetness,newQueue));
  }

}

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.

StackExchange Code Review Q#118816, answer score: 10