5
\$\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\$
8
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. Did'nt know about inbuilt priority queue. All my test cases are working. \$\endgroup\$ – user3324848 Feb 4 '16 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\$ – greybeard Dec 26 '16 at 11:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.