Jesse and Cookies| Heap
Task(Easy)
Jesse loves cookies and wants the sweetness of some cookies to be greater than value fr. To do this, two cookies with the least sweetness are repeatedly mixed. This creates a special combined cookle with:
sweetness (1x Least sweet cookie + 2x 2nd least sweet cookie).
This occurs until all the cookies have a sweetness ≥k.
Given the sweatness of a number of cookies, determine the minimum number of operations required. If it is not possible, return -1.
Example
k = 9 A = [2, 7, 3, 6, 4, 6] The smallest values are 2, 3. Remove them then return 2 + 2 * 3 = 8 to the array, Now A = [8, 7, 6, 4, 6] A = [16, 8, 7, 6] Remove 4, 6 and return 4 + 6 * 2 = 16 to the array. Now Remove 6, 7. return 6 + 2 * 7 = 20 and A = [20, 10, 8, 7] Finally, remove 8, 7 and return 7 + 2 * 8 = 23 to A. Now A = [23, 20, 10] All values are >= k = 0 so the process stops after 4 iterations. Return 4.
Function Description
Complete the cookies function in the editor below.
cookies has the following parameters:
int k: the threshold value
int Aln): an array of sweetness values
Returns
• int: the number of iterations required or -1
Input Format
The first line has two space-separated integers, a and le. the size of Al] and the minimum required sweetness respectively.
The next line contains space-separated integers, A[1].
Constraints
1≤ n ≤ 100
0≤ k ≤ 10
0≤100
Sample Input
STDIN
67
1 2 3 9 10 12
Function
A[] size n6, k7
A= [1, 2, 3, 9, 10, 12]
Sample Output
2
Explanation
Combine the first two cookies to create a cookie with sweetness =1x1+2x2=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=1x3+2x5=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
import heapq
def cookies(k, A):
heapq.heapify(A)
minVal = heapq.heappop(A)
if minVal >= k:
return 0
heapq.heappush(A, minVal)
count = 0
while(len(A) >= 2):
min1 = heapq.heappop(A)
min2 = heapq.heappop(A)
heapq.heappush(A, min1 + min2 * 2)
count += 1
minNew = heapq.heappop(A)
if minNew >= k:
return count
heapq.heappush(A, minNew)
return -1
