6
\$\begingroup\$

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<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?

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

1 Answer 1

Reset to default
10
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks a lot. Did'nt know about inbuilt priority queue. All my test cases are working. \$\endgroup\$ Commented Feb 4, 2016 at 17:03
  • \$\begingroup\$ (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"ß \$\endgroup\$ Commented Dec 26, 2016 at 11:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.