Jesse and Cookies, Hackerrank

In this blog, we will discuss a problem Jesse loves cookies or jesse and cookies mentioned on Hackerrank

Problem Statement

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

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

He repeats this procedure until all the cookies in his collection have a sweetness .
You are given Jesse’s cookies. Print the number of operations required to give the cookies a sweetness . Print  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 A[i] is the sweetness of the i cookie in Jesse’s collection.

Constraints
1 <= N <= 10^6
0 <= K <= 10^9
1 <= A[i] <= 10^6

Output Format
Output the number of operations that are needed to increase the cookie’s sweetness .
Output -1 if this isn’t possible.

Sample Input
6 7
1 2 3 9 10 12

Sample Output
2

Explanation
Combine the first two cookies to create a cookie with sweetness  = 1 x 1 + 2 x 2 = 5
After this operation, the cookies are : 3, 5, 9, 10, 12
Then, combine the cookies with sweetness 3 and sweetness 5, to create a cookie with resulting sweetness  = 1 x 3 + 2 x 5 = 13
Now, the cookies are : 9, 10, 12, 13
All the cookies have a sweetness >= 7

Thus, 2 operations are required to increase the sweetness.


Solution : Jesse and Cookies

The given problem statement is simple to understand. We need to check if there is any number present in the given array which is less than K, and if present, then convert it into another number using the sweetness formula given.

Here, only one sample input is given which is sorted, but it is not mentioned anywhere in the problem that you will be given a sorted array. So, you need to think of a solution keeping in mind that array could be unsorted.

Here are more sample inputs for you to think through it.

Sample Input
3 10
1 1 1

Sample Output
-1

Sample Input
2 10
11 67 42

Sample Output
0

Hint : You can use heap data structure here.

Logic

You need to have a knowledge of heaps and its working before moving onto the logic.

As we need to check only for the values lesser than the given K, we can take advantage of min-heaps here.

Min heap is a data structure in which minimum values are always present on the top, and you can create them by using Priority Queue in Java.

  1. Add all values of an array to the min heap.
  2. Check if top of heap has the value less than k.
    • If yes, then poll first two values from heap
    • Calculate using the given formula and add it to heap
    • Repeat step 2, till top of heap becomes greater or equal to K.

Code implementation

Various operations are supported by heaps and each them is very efficient in terms of time complexity.

We used following operations here –

  • peek() : O(1)
  • add() : O(log n)
  • poll() : O(1)

And in addition to it we are copying each item from array to min heap which means we are traversing all items once.

Time Complexity

So, the overall time complexity of this solution is O(n).

button

Let me know your feedback and don’t forget to subscribe.

Happy learning. Happy Coding.


Leave a Reply