Hacker rank Jesse and Cookies

Question

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 =(×ばつ Least sweet cookie + ×ばつ 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<Integer> newList){
 Collections.sort(newList);
 int count=0;
 while(newList.getFirst()<k){
 if(newList.size()>=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 Solution();
 Scanner scanObj = new Scanner(System.in);
 int numOfCookies = scanObj.nextInt();
 long minSweetness = scanObj.nextLong();
 LinkedList<Integer> newList = new LinkedList<Integer>();
 for(int i=0;i<numOfCookies;i++){
 newList.add(scanObj.nextInt());
 }
 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?

• Jesse C. Slicer: Not really a big fan of cookies, btw.
• yavuzkavus: You may check: stackoverflow.com/a/57317912/1856618

Answer 1

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.

---

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<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);
 int numOfCookies = scanObj.nextInt();
 long minSweetness = scanObj.nextLong();
 PriorityQueue<Integer> newQueue = new PriorityQueue<Integer>();
 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.

• user3324848: Thanks a lot. Did'nt know about inbuilt priority queue. All my test cases are working.
• greybeard: (Directly implementing "Jesse's procedure",) Do you need a priority queue? Processing the cookies in increasing order, what can be said about the "sweetness series" of the "combined cookies"ß