Aditya has arranged some of his building blocks in N columns. Each column has a certain number of blocks given by an array A.
Each element of A(i.e. Ai) is the height of the ith column. Aditya now has M blocks left. He doesn't like small columns.
So he wants to maximize the minimum of all heights. He may or may not use all of the M blocks.
Determine the maximized height.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {1, 2, 3, 4, 5} and M = 6 
Output : 4
Explanation:
Final heights of blocks - 4 4 4 4 5
Ã¢â¬â¹Example 2:
Input : arr[ ] = {2, 8, 9} and M = 4 
Output :  6
Explanation:
Final heights of blocks - 6 8 9 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maximised_height() that takes an array (arr), sizeOfArray (n), an integer M and return the maximized height. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
 
Output : 
For each test case, print the required answer in a new line.
Constraints :
1 ≤ N ≤ 10^{5}
1 ≤ M ≤ 10^{4}
1 ≤ Ai ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



def maximised_height (arr, n, m) : 

    #Complete the function



Solutions:
def maximised_height(arr, n, m):
	lo = min(arr)
	hi = max(arr) + m
	ans = -1
	while lo <= hi:
		mi = (lo + hi) // 2
		if ok(arr, n, mi, m):
			ans = mi
			lo = mi + 1
		else:
			hi = mi - 1
	return ans

def ok(a, n, mi, m):
	ans = 0
	for i in range(n):
		if a[i] < mi:
			ans += mi - a[i]
	return ans <= m


import heapq

def maximised_height(arr, n, m):
	heapq.heapify(arr)
	count = 1
	while arr and m >= count:
		item = heapq.heappop(arr)
		while arr and item < arr[0] and (m >= count):
			item += 1
			m -= count
		count += 1
	if not arr:
		count -= 1
	while m >= count:
		item += 1
		m -= count
	return item