There are N bags with diamonds in them. The i'th of these bags contains A[i] diamonds. If you drop a bag with A[i] diamonds, it changes to A[i]/2 diamonds and you gain A[i] diamonds. Dropping a bag takes 1 minute. Find the maximum number of diamonds that you can take if you are given K minutes.
Example 1:
Input:
N = 5, K = 3
A[] = {2, 1, 7, 4, 2}
Output:
14
Explanation:
The state of bags is:
2 1 7 4 2
You take all diamonds from Third bag (7).
The state of bags becomes: 2 1 3 4 2 
Take all diamonds from Fourth bag (4).
The state of bags becomes: 2 1 3 2 2
Take all diamonds from Third bag (3).
The state of bags becomes: 2 1 1 2 2 
Hence, number of Diamonds = 7+4+3 = 14.
Example 2:
Input:
N = 3, K = 2
A[] = {7, 1, 2}
Output:
10
Explanation:
You take all diamonds from First bag (7).
The state of bags becomes: 3 1 2 
Take all diamonds from again First bag (3).
The state of bags becomes: 1 1 2
You can take a maximum of 10 diamonds.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxDiamonds() which takes 2 Integers N, and K and an integer and an array A[] of N integers as input and returns the maximum number of diamonds you can take in K minutes.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
0 <= K,A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def maxDiamonds(self, A, N, K):

        # code here 

Solutions:
import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		maxheap = []
		su = 0
		for i in range(0, N):
			heapq.heappush(maxheap, -A[i])
		while K > 0:
			ele = -heapq.heappop(maxheap)
			su += ele
			a = ele // 2
			heapq.heappush(maxheap, -a)
			K -= 1
		return su


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		maxheap = []
		gain = 0
		temp = 0
		temp1 = 0
		for i in A:
			heapq.heappush(maxheap, -i)
		while K != 0:
			temp = -heapq.heappop(maxheap)
			gain = gain + temp
			temp = temp // 2
			heapq.heappush(maxheap, -temp)
			K = K - 1
		return gain


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		maxheap = []
		gain = 0
		temp = 0
		for i in range(0, N):
			heapq.heappush(maxheap, -A[i])
		while K > 0:
			temp = -heapq.heappop(maxheap[0])
			gain = gain + temp
			temp = temp // 2
			heapq.heappush(maxheap, -temp)
			K = K - 1
		return gain
import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		n = 0
		m = 0
		s = 0
		heap1 = []
		for i in A:
			heapq.heappush(heap1, -i)
		heapq.heapify(heap1)
		while K != 0:
			n = -heapq.heappop(heap1)
			s += n
			m = -(n // 2)
			heapq.heappush(heap1, m)
			K -= 1
		return s


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		n = 0
		m = 0
		s = 0
		heap1 = []
		for i in A:
			heapq.heappush(heap1, -i)
		while K != 0:
			n = -heapq.heappop(heap1)
			s += n
			m = -(n // 2)
			heapq.heappush(heap1, m)
			K -= 1
		return s


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		h = []
		for i in A:
			heapq.heappush(h, -1 * i)
		res = 0
		while K:
			temp = heapq.heappop(h)
			res += abs(temp)
			temp = -1 * (abs(temp) // 2)
			heapq.heappush(h, temp)
			K -= 1
		return res


import heapq

class Solution:

	def maxDiamonds(self, arr, n, k):
		heap1 = []
		m = 0
		d = 0
		s = 0
		for i in arr:
			heapq.heappush(heap1, -i)
		heapq.heapify(heap1)
		while k != 0:
			m = -heapq.heappop(heap1)
			s += m
			d = -(m // 2)
			heapq.heappush(heap1, d)
			k -= 1
		return s


class Solution:

	def maxDiamonds(self, A, N, K):
		import heapq
		import math

		def negate(num):
			return -num
		A = list(map(negate, A))
		heapq.heapify(A)
		diamonds = 0
		while K > 0:
			val = heapq.heappop(A)
			diamonds += val
			heapq.heappush(A, math.ceil(val / 2))
			K -= 1
		return -diamonds


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		heap = []
		heapq.heapify(heap)
		for i in range(N):
			heapq.heappush(heap, -1 * A[i])
		total = 0
		for i in range(K):
			total += -1 * heap[0]
			p = -1 * heap[0] // 2
			heapq.heappop(heap)
			heapq.heappush(heap, -1 * p)
		return total


class Solution:

	def maxDiamonds(self, A, N, K):
		(arr, n, k) = (A, N, K)
		import heapq
		pq = []
		ans = 0
		for i in arr:
			heapq.heappush(pq, -i)
		for i in range(k):
			el = -heapq.heappop(pq)
			ans += el
			heapq.heappush(pq, -(el // 2))
		return ans


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		res = 0
		heapq._heapify_max(A)
		while K:
			temp = heapq._heappop_max(A)
			res += temp
			A.append(temp // 2)
			K -= 1
		return res


import heapq

class Solution:

	def maxDiamonds(self, A, n, K):
		ans = 0
		heapq._heapify_max(A)
		while K:
			temp = heapq._heappop_max(A)
			ans += temp
			A.append(temp // 2)
			K -= 1
		return ans


import heapq

class Solution:

	def maxDiamonds(self, A, n, K):
		summ = 0
		heapq._heapify_max(A)
		for i in range(K):
			p = heapq._heappop_max(A)
			summ += p
			A.append(p // 2)
		return summ


import heapq

class Solution:

	def maxDiamonds(self, arr, n, K):
		pq = []
		heapq.heapify(pq)
		ans = 0
		for i in arr:
			heapq.heappush(pq, -1 * i)
		while K:
			temp = heapq.heappop(pq)
			temp = -1 * temp
			ans += temp
			heapq.heappush(pq, -1 * (temp // 2))
			K -= 1
		return ans


from collections import deque

class Solution:

	def maxDiamonds(self, A, N, K):
		if K == 0:
			return 0
		A.sort()
		result = A.pop()
		stack = deque([result // 2])
		K -= 1
		for _ in range(K):
			if A and A[-1] > stack[-1]:
				item = A.pop()
			else:
				item = stack.pop()
			result += item
			stack.appendleft(item // 2)
		return result


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		sum = 0
		heapq._heapify_max(A)
		for i in range(K):
			p = heapq._heappop_max(A)
			sum += p
			A.append(p // 2)
		return sum


from heapq import heappush, heappop

class Solution:

	def maxDiamonds(self, a, n, k):
		ans = 0
		h = []
		for i in range(n):
			heappush(h, -1 * a[i])
		while h and k > 0:
			t = -heappop(h)
			ans += t
			heappush(h, -(t // 2))
			k -= 1
		return ans


import bisect

class Solution:

	def maxDiamonds(self, A, N, K):
		c = 0
		s = 0
		A.sort()
		while c != K:
			a = A[-1]
			A.pop()
			s += a
			bisect.insort(A, a // 2)
			c += 1
		return s


from heapq import *

class Solution:

	def maxDiamonds(self, A, N, K):
		maxheap = []
		sumq = 0
		for i in A:
			heappush(maxheap, -i)
		for j in range(K):
			gg = -heappop(maxheap)
			heappush(maxheap, -(gg // 2))
			sumq = sumq + gg
		return sumq


from heapq import heappop, heappush, heapify

class Solution:

	def maxDiamonds(self, A, N, K):
		pq = []
		heapify(pq)
		for i in A:
			heappush(pq, -1 * i)
		ans = 0
		while K:
			ele = heappop(pq)
			ele = -1 * ele
			ans += ele
			heappush(pq, -1 * (ele // 2))
			K -= 1
		return ans


from heapq import heappop, heappush, heapify
from math import ceil

class Solution:

	def maxDiamonds(self, a, n, k):
		for i in range(n):
			a[i] = -1 * a[i]
		ans = 0
		heapify(a)
		for _ in range(k):
			ele = heappop(a)
			heappush(a, int(ceil(ele / 2)))
			ans += -1 * ele
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def maxDiamonds(self, A, N, K):
		temp = []
		heapify(temp)
		for i in range(N):
			heappush(temp, -1 * A[i])
		res = 0
		while K > 0:
			val = -1 * heappop(temp)
			res += val
			val = val // 2
			heappush(temp, -1 * val)
			K -= 1
		return res


class Solution:

	def maxDiamonds(self, A, N, K):
		import heapq
		for i in range(N):
			A[i] = -1 * A[i]
		heapq.heapify(A)
		diamonds = 0
		for i in range(K):
			bag = heapq.heappop(A)
			diamonds += bag
			heapq.heappush(A, -1 * (bag // -2))
		return -1 * diamonds


from heapq import *

class Solution:

	def maxDiamonds(self, A, N, K):
		maxHeap = []
		for i in A:
			heappush(maxHeap, -i)
		ans = 0
		while K > 0:
			gg = -heappop(maxHeap)
			a = gg // 2
			heappush(maxHeap, -a)
			ans += gg
			K -= 1
		return ans


from heapq import heappop, heappush, heapify

class Solution:

	def maxDiamonds(self, A, N, K):
		b = []
		heapify(b)
		for i in A:
			heappush(b, -1 * i)
		s = 0
		for i in range(K):
			a = heappop(b)
			a = a // -1
			s += a
			a = a // 2
			heappush(b, -1 * a)
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxDiamonds(A, N, K))


from heapq import _heapify_max as heapify
from heapq import _heappop_max as popmax

class Solution:

	def maxDiamonds(self, A, N, K):
		heapify(A)
		ans = 0
		for _ in range(K):
			max_1 = popmax(A)
			ans += max_1
			max_half = max_1 // 2
			A.append(max_half)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxDiamonds(A, N, K))


from heapq import heapify, heappop, heappush

class Solution:

	def maxDiamonds(self, a, n, k):
		for i in range(n):
			a[i] = a[i] * -1
		heapify(a)
		gain = 0
		while k:
			num = heappop(a)
			num *= -1
			gain += num
			num = num // 2
			num *= -1
			heappush(a, num)
			k -= 1
		return gain
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxDiamonds(A, N, K))


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		for i in range(N):
			A[i] = -1 * A[i]
		heapq.heapify(A)
		c = 0
		while K:
			l = -1 * heapq.heappop(A)
			c += l
			heapq.heappush(A, -1 * int(l / 2))
			K -= 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxDiamonds(A, N, K))


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		summ = 0
		heapq._heapify_max(A)
		for i in range(K):
			p = heapq._heappop_max(A)
			summ += p
			A.append(p // 2)
		return summ
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxDiamonds(A, N, K))


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		dia = []
		heapq.heapify(dia)
		for i in range(N):
			heapq.heappush(dia, -1 * A[i])
		largest = 0
		while K > 0:
			temp = heapq.heappop(dia)
			temp *= -1
			largest += temp
			heapq.heappush(dia, -1 * (temp // 2))
			K -= 1
		return largest


import heapq
import math

class Solution:

	def maxDiamonds(self, A, N, K):
		heap = []
		heapq.heapify(heap)
		for i in A:
			heapq.heappush(heap, -1 * i)
		diamond = 0
		while K:
			temp = -1 * heapq.heappop(heap)
			diamond += temp
			temp = int(math.floor(temp / 2))
			heapq.heappush(heap, -1 * temp)
			K -= 1
		return diamond


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		for i in range(N):
			if A[i] != 0:
				A[i] = A[i] * -1
		heapq.heapify(A)
		totcost = 0
		j = 0
		while j < K:
			temp = heapq.heappop(A)
			heapq.heappush(A, int(temp / 2))
			totcost += temp * -1
			j += 1
		return totcost


import heapq
from heapq import heappush, heappop, heapify

class Solution:

	def maxDiamonds(self, A, N, K):
		x = []
		heapify(x)
		for i in A:
			heappush(x, -1 * i)
		c = 0
		while K:
			temp = -1 * heappop(x)
			c += temp
			heappush(x, -1 * (temp // 2))
			K -= 1
		return c


import heapq

class Solution:

	def maxDiamonds(self, A, N, K):
		save = []
		for i in A:
			save.append(-i)
		heapq.heapify(save)
		ans = 0
		while K > 0:
			K -= 1
			temp = -heapq.heappop(save)
			heapq.heappush(save, -(temp // 2))
			ans += temp
		return ans


import heapq

class Solution:

	def maxDiamonds(self, a, n, k):
		a = [-1 * x for x in a]
		heapq.heapify(a)
		sum = 0
		while k > 0:
			x = heapq.heappop(a)
			sum += x * -1
			heapq.heappush(a, -1 * x // 2 * -1)
			k -= 1
		return sum


class Solution:

	def heapify(self, heap, i):
		if i > len(heap) // 2 - 1:
			return
		largest = i
		l = 2 * i + 1
		r = 2 * i + 2
		if l < len(heap) and A[l] > A[largest]:
			largest = l
		if r < len(heap) and A[r] > A[largest]:
			largest = r
		if largest != i:
			(A[largest], A[i]) = (A[i], A[largest])
		else:
			return
		self.heapify(heap, largest)

	def maxDiamonds(self, A, N, K):
		for i in range(N // 2 - 1, -1, -1):
			self.heapify(A, i)
		result = 0
		for i in range(K):
			result += A[0]
			A[0] = A[0] // 2
			self.heapify(A, 0)
		return result


import heapq
import math

class Solution:

	def maxDiamonds(self, a, n, k):
		res = 0
		for i in range(n):
			a[i] = -a[i]
		heapq.heapify(a)
		for _ in range(k):
			val = heapq.heappop(a)
			res += val
			if val & 1:
				heapq.heappush(a, val // 2 + 1)
			else:
				heapq.heappush(a, val // 2)
		return -res


from queue import PriorityQueue

class Solution:

	def maxDiamonds(self, a, n, k):
		q = PriorityQueue()
		for i in a:
			q.put(-1 * i)
		ans = 0
		while k:
			temp = q.get() * -1
			ans += temp
			q.put(-1 * (temp // 2))
			k -= 1
		return 1 * ans