There are n trees in a forest. The heights of the trees is stored in array tree[], where tree[i] denotes the height of the i^{th} tree in the forest. If the i^{th} tree is cut at a height H, then the wood collected is tree[i] - H, provided tree[i] > H. If the total woods that needs to be collected is exactly equal to k, find the height H at which every tree should be cut (all trees have to be cut at the same height). If it is not possible then return -1 else return H.
Example 1:
Input:
n = 5, k = 4
tree[] = {2, 3, 6, 2, 4}
Output: 3
Explanation: Wood collected by cutting trees
at height 3 = 0 + 0 + (6-3) + 0 + (4-3) = 4
hence 3 is to be subtracted from all numbers.
Since 2 is lesser than 3, nothing gets
subtracted from it.
Example 2:
Input:
n = 6, k = 8
tree[] = {1, 7, 6, 3, 4, 7}
Output: 4
Explanation: Wood collected by cutting trees
at height 4 = 0+(7-4)+(6-4)+0+0+(7-4) = 8
Your Task:
Your task is to complete the function find_height(). This function takes the array tree[ ], and the integers n and k as input parameters and returns the height at which trees have to be cut. If no positive integer value of height is possible, return -1.
Expected Time Complexity: O(n log h)
Expected Auxiliary Space: O(1)
Constraints: 
1 <= n <= 10^{4}
1 <= tree[i] <= 10^{3}
1 <= k <= 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: class Solution:

    def find_height(self,tree,n,k):

        # code here

Solutions:
class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		n = len(tree)
		low = 1
		high = tree[n - 1]
		while low <= high:
			mid = (low + high) // 2
			c = 0
			for i in range(n):
				if tree[i] - mid > 0:
					c += tree[i] - mid
			if c == k:
				return mid
			elif c > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		(low, high) = (0, max(tree))
		while low <= high:
			mid = (low + high) // 2
			sm = 0
			for i in tree:
				sm += i - mid if i > mid else 0
			if sm == k:
				return mid
			elif sm > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		h = max(tree)
		l = 0
		while l <= h:
			mid = (h + l) // 2
			summ = 0
			for i in range(n):
				if tree[i] - mid > 0:
					summ += tree[i] - mid
			if summ == k:
				return mid
			elif summ > k:
				l = mid + 1
			elif summ < k:
				h = mid - 1
		return -1


def mgc(arr, x):
	ans = 0
	for i in arr:
		if x > i:
			ans += 0
		else:
			ans += i - x
	return ans

class Solution:

	def find_height(self, tree, n, k):
		(st, en) = (0, max(tree))
		while st <= en:
			mid = (st + en) // 2
			temp = mgc(tree, mid)
			if temp > k:
				st = mid + 1
			elif temp < k:
				en = mid - 1
			else:
				return mid
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		limit = tree[n - 1]
		cut = 0
		while cut <= limit:
			mid = cut + (limit - cut) // 2
			su = 0
			for i in range(n):
				if tree[i] < mid:
					continue
				su += tree[i] - mid
			if su == k:
				return mid
			elif su > k:
				cut = mid + 1
			else:
				limit = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):

		def isPossible(mid):
			total = 0
			for i in range(n):
				if mid < tree[i]:
					total += tree[i] - mid
			return total
		l = 0
		r = max(tree) - 1
		while l <= r:
			mid = (l + r) // 2
			count = isPossible(mid)
			if count == k:
				return mid
			elif count > k:
				l = mid + 1
			elif count < k:
				r = mid - 1
		return -1


class Solution:

	def find_height(self, arr, n, k):

		def ispossible(currh, need):
			woods = 0
			for i in range(0, n):
				if arr[i] - currh > 0:
					woods += arr[i] - currh
			if woods == need:
				return 1
			elif woods > need:
				return 0
			else:
				return -1
		maxh = max(arr)
		start = 0
		end = maxh
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			d = ispossible(mid, k)
			if d == 1:
				return mid
			if d == 0:
				start = mid + 1
			else:
				end = mid - 1
		return ans


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			y = 0
			for i in range(mid, n):
				y += tree[i] - tree[mid]
			if y < k:
				h = mid - 1
			elif y == k:
				return tree[mid]
			else:
				l = mid + 1
		p = 0
		for i in range(l, n):
			p += tree[i]
		ans = (p - k) / (n - l)
		if ans == (p - k) // (n - l):
			return int(ans)
		return -1


class Solution:

	def woodcollect(self, tree, n, k, mid):
		wood = 0
		for i in range(n - 1, -1, -1):
			if tree[i] - mid < 0:
				break
			wood += tree[i] - mid
		return wood

	def find_height(self, tree, n, k):
		if n == 1:
			if tree[0] > k:
				return tree[0] - k
			else:
				return -1
		tree.sort()
		low = tree[0]
		high = tree[-1]
		mid = (low + high) // 2
		while low <= high:
			mid = low + (high - low) // 2
			wood = self.woodcollect(tree, n, k, mid)
			if wood == k:
				return mid
			if wood > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def solve(self, tree, n, height):
		count = 0
		for i in tree:
			if i > height:
				count += i - height
		return count

	def find_height(self, tree, n, k):
		low = 1
		high = max(tree)
		while low <= high:
			mid = (low + high) // 2
			woods = self.solve(tree, n, mid)
			if woods == k:
				return mid
			elif woods < k:
				high = mid - 1
			else:
				low = mid + 1
		return -1


class Solution:

	def bn(self, arr, mid):
		diff = 0
		for i in arr:
			if i >= mid:
				diff += i - mid
		return diff

	def find_height(self, tree, n, k):
		s = 0
		e = 100000
		mid = (s + e) // 2
		ans = -1
		while s <= e:
			if self.bn(tree, mid) == k:
				ans = mid
				return ans
			elif self.bn(tree, mid) > k:
				s = mid + 1
			else:
				e = mid - 1
			mid = (s + e) // 2
		return ans


class Solution:

	def find_height(self, tree, n, k):
		l = 0
		h = max(tree)
		cut = 0
		while l <= h:
			mid = l + h >> 1
			cut = 0
			for i in range(n):
				if tree[i] <= mid:
					continue
				cut += tree[i] - mid
			if cut == k:
				return mid
			elif cut > k:
				l = mid + 1
			else:
				h = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		l = 1
		r = max(tree)
		while l <= r:
			cut = (l + r) // 2
			wood = 0
			for i in range(n):
				if tree[i] > cut:
					wood += tree[i] - cut
			if wood == k:
				return cut
			elif wood > k:
				l = cut + 1
			else:
				r = cut - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		low = 0
		high = max(tree)
		while low < high:
			mid = (low + high) // 2
			summa = 0
			for item in tree:
				cut = item - mid
				if cut > 0:
					summa += cut
			if summa == k:
				return mid
			if summa > k:
				low = mid + 1
			else:
				high = mid - 1
		return low if sum((max(0, item - low) for item in tree)) == k else -1


class Solution:

	def find_height(self, tree, n, k):
		s = 0
		e = max(tree)
		while s <= e:
			m = s + (e - s) // 2
			res = 0
			for i in range(n):
				if tree[i] > m:
					res += tree[i] - m
			if res == k:
				return m
			elif res > k:
				s = m + 1
			else:
				e = m - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		l = 0
		h = max(tree)
		while l <= h:
			mid = (l + h) // 2
			cnt = 0
			for i in tree:
				if i >= mid:
					cnt += i - mid
			if cnt == k:
				return mid
			elif cnt > k:
				l = mid + 1
			else:
				h = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		(lo, hi) = (1, max(tree))
		while lo <= hi:
			height = (lo + hi) // 2
			accum = 0
			for t in tree:
				if t > height:
					accum += t - height
				if accum > k:
					break
			if accum == k:
				return height
			elif accum < k:
				hi = height - 1
			else:
				lo = height + 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		s = 0
		tree.sort()
		e = tree[n - 1]
		while s <= e:
			mid = (s + e) // 2
			si = 0
			for i in range(n - 1, -1, -1):
				if tree[i] - mid <= 0:
					break
				si += tree[i] - mid
			if si < k:
				e = mid - 1
			elif si > k:
				s = mid + 1
			else:
				return mid
		return -1


class Solution:

	def find_height(self, arr, n, k):
		low = 1
		high = max(arr)
		while low <= high:
			mid = low + (high - low) // 2
			count = 0
			for i in range(len(arr)):
				if arr[i] > mid:
					count += arr[i] - mid
			if count == k:
				return mid
			if count > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		l = 1
		h = max(tree)
		while l <= h:
			c = 0
			mid = (l + h) // 2
			for i in range(n - 1, -1, -1):
				if tree[i] - mid <= 0:
					break
				c += tree[i] - mid
			if c == k:
				return mid
			elif c < k:
				h = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		low = 0
		high = n - 1
		ans = -1
		while low <= high:
			mid = int((low + high) / 2)
			out = 0
			for i in range(mid, n):
				out += tree[i] - tree[mid]
			if k == out:
				ans = tree[mid]
				break
			elif k < out:
				low = mid + 1
			else:
				high = mid - 1
		if ans == -1:
			temp_out = 0
			for i in range(high + 1, n):
				temp_out += tree[i]
			out = (temp_out - k) / (n - high - 1)
			if out % 1 == 0:
				return int(out)
			return -1
		else:
			return ans


class Solution:

	def find_height(self, tree, n, k):
		maxh = max(tree)

		def binary_search(l, r):
			if l > r:
				return -1
			mid = int((l + r) / 2)
			cut_woods = 0
			for i in tree:
				cut_woods += i - mid if i - mid > 0 else 0
			if cut_woods == k:
				return mid
			if cut_woods < k:
				return binary_search(l, mid - 1)
			else:
				return binary_search(mid + 1, r)
		return binary_search(0, maxh)


class Solution:

	def res(self, tree, n, mid):
		summ = 0
		for i in range(n - 1, -1, -1):
			if tree[i] - mid <= 0:
				break
			else:
				summ += tree[i] - mid
		return summ

	def find_height(self, tree, n, k):
		tree.sort()
		low = 0
		high = tree[n - 1]
		while low <= high:
			mid = low + int((high - low) / 2)
			collect = self.res(tree, n, mid)
			if collect == k:
				return mid
			if collect > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def wood_collected(self, tree, n, mid):
		sum = 0
		for i in range(n - 1, -1, -1):
			if tree[i] - mid <= 0:
				break
			sum += tree[i] - mid
		return sum

	def find_height(self, tree, n, k):
		tree = sorted(tree)
		left = 0
		right = max(tree)
		wood = 0
		while left <= right:
			mid = (left + right) // 2
			wood = self.wood_collected(tree, n, mid)
			if wood == k:
				return mid
			elif wood < k:
				right = mid - 1
			else:
				left = mid + 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree = sorted(tree)
		low = tree[0]
		high = tree[n - 1]
		if n == 1:
			return tree[0] - k
		while low <= high:
			mid = (high + low) // 2
			sum = 0
			for i in range(n):
				if mid < tree[i]:
					sum += tree[i] - mid
			if k == sum:
				return mid
			elif k < sum:
				low = mid + 1
			elif k > sum:
				high = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		mx = max(tree)
		mi = 1
		while mi <= mx:
			mid = (mi + mx) // 2
			wood_collected = 0
			for i in tree:
				if i > mid:
					wood_collected = wood_collected + (i - mid)
			if wood_collected == k:
				return mid
			elif wood_collected > k:
				mi = mid + 1
			else:
				mx = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		s = 0
		e = 10000
		ans = -1
		while s <= e:
			mid = s + (e - s) // 2
			if self.solve(tree, mid) == k:
				ans = mid
				break
			if self.solve(tree, mid) < k:
				e = mid - 1
			else:
				s = mid + 1
		return ans

	def solve(self, arr, mid):
		diff = 0
		for i in arr:
			if i >= mid:
				diff += i - mid
		return diff


class Solution:

	def find_height(self, tree, n, k):

		def ispossible(H, tree, k):
			woods = 0
			for i in range(0, n):
				if tree[i] - H >= 0:
					woods += tree[i] - H
			if woods == k:
				return 1
			elif woods > k:
				return 0
			else:
				return -1
		start = 0
		end = max(tree)
		ans = -1
		while start <= end:
			mid = start + end >> 1
			d = ispossible(mid, tree, k)
			if d == 1:
				return mid
			elif d == 0:
				start = mid + 1
			else:
				end = mid - 1
		return ans


class Solution:

	def woodcollected(self, tree, k):
		wood = 0
		for i in range(len(tree)):
			if tree[i] >= k:
				wood += tree[i] - k
		return wood

	def binarysearch(self, l, r, k, tree):
		if l <= r:
			mid = (l + r) // 2
			w = self.woodcollected(tree, mid)
			if w == k:
				return mid
			elif w > k:
				return self.binarysearch(mid + 1, r, k, tree)
			else:
				return self.binarysearch(l, mid - 1, k, tree)
		return -1

	def find_height(self, tree, n, k):
		return self.binarysearch(0, max(tree), k, tree)


class Solution:

	def find_height(self, tree, n, k):
		tree.sort(reverse=True)
		temp_k = 0
		index = 0
		for i in range(max(tree) - 1, 0, -1):
			while index < n and i < tree[index]:
				index += 1
			temp_k += index
			if temp_k == k:
				return i
			elif temp_k > k:
				return -1
		return -1


class Solution:

	def find_height(self, arr, n, k):
		arr.sort()
		(l, h) = (0, arr[-1])
		while l < h:
			m = (l + h) // 2
			c = 0
			i = n - 1
			while i > -1 and arr[i] > m:
				c += arr[i] - m
				i = i - 1
			if c == k:
				return m
			elif c < k:
				h = m
			else:
				l = m + 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		left = 0
		right = tree[-1]
		res = float('inf')
		while left <= right:
			mid = (left + right) // 2
			total = 0
			for x in tree:
				if x > mid:
					total += x - mid
			if total == k:
				res = min(mid, res)
			if total < k:
				right = mid - 1
			else:
				left = mid + 1
		if res == float('inf'):
			return -1
		else:
			return res


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		if len(tree) == 1:
			return tree[0] - k
		s = tree[0]
		m = tree[n - 1]
		while s <= m:
			mid = s + (m - s) // 2
			collected = sum([h - mid for h in tree if h > mid])
			if collected == k:
				return mid
			elif collected > k:
				s = mid + 1
			elif collected < k:
				m = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		i = 0
		j = tree[-1]
		while i <= j:
			m = (i + j) // 2
			sum = 0
			for l in range(n):
				if tree[l] >= m:
					sum += tree[l] - m
			if sum == k:
				return m
			elif sum < k:
				j = m - 1
			else:
				i = m + 1
		return -1


class Solution:

	def check(self, tree, mid):
		wood = 0
		for i in tree:
			if i > mid:
				wood = wood + i - mid
		return wood

	def find_height(self, tree, n, k):
		l = 0
		h = max(tree)
		while l <= h:
			mid = l + h >> 1
			wood = self.check(tree, mid)
			if wood == k:
				return mid
			elif wood > k:
				l = mid + 1
			else:
				h = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree = sorted(tree)
		h_start = 0
		h_end = tree[n - 1]
		while h_start <= h_end:
			mid = h_start + (h_end - h_start) // 2
			collected_wood = 0
			for i in range(n - 1, -1, -1):
				if tree[i] < mid:
					break
				collected_wood += tree[i] - mid
			if collected_wood == k:
				return mid
			elif collected_wood > k:
				h_start = mid + 1
			else:
				h_end = mid - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		left = 0
		right = 1000
		ans = -1
		while left <= right:
			mid = (left + right) // 2
			sum1 = 0
			for i in range(n):
				if tree[i] >= mid:
					sum1 += tree[i] - mid
			if sum1 > k:
				left = mid + 1
			elif sum1 < k:
				right = mid - 1
			else:
				return mid
		return ans


class Solution:

	def find_height(self, tree, n, k):
		if len(tree) == 1:
			if tree[0] > k:
				return tree[0] - k
		ans = -1

		def canThisBeHeight(Height, trees):
			woodCollected = 0
			for treeH in trees:
				if treeH > Height:
					woodCollected += treeH - Height
			return woodCollected
		start = min(tree)
		end = max(tree)
		mid = (start + end) // 2
		while start <= end:
			woodCollection = canThisBeHeight(mid, tree)
			if woodCollection < k:
				end = mid - 1
			elif woodCollection > k:
				start = mid + 1
			else:
				return mid
			mid = (start + end) // 2
		return ans


class Solution:

	def find_height(self, tree, n, k):

		def solve(self, arr, mid, n):
			su = 0
			for i in range(n):
				if tree[i] > mid:
					su += tree[i] - mid
			return su
		(s, e) = (0, 0)
		for i in range(n):
			e = max(e, tree[i])
		while s <= e:
			mid = int((s + e) / 2)
			su = solve(self, tree, mid, n)
			if su == k:
				return mid
			elif su < k:
				e = mid - 1
			else:
				s = mid + 1
		return -1


class Solution:

	def solve(self, arr, mid):
		diff = 0
		for i in arr:
			if i >= mid:
				diff += i - mid
		return diff

	def find_height(self, tree, n, k):
		l = 0
		r = max(tree)
		ans = -1
		while l <= r:
			mid = l + (r - l) // 2
			if self.solve(tree, mid) == k:
				ans = mid
				break
			elif self.solve(tree, mid) < k:
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def find_height(self, tree, n, k):
		high = max(tree)
		low = 0
		while low <= high:
			mid = (low + high) // 2
			wood = self.cut(mid, tree)
			if wood == k:
				return mid
			elif wood > k:
				low = mid + 1
			else:
				high = mid - 1
		return -1

	def cut(self, h, tree):
		s = 0
		for ele in tree:
			if ele > h:
				s += ele - h
		return s


class Solution:

	def fun(self, a, k, m):
		c = 0
		for i in a:
			if i <= m:
				continue
			else:
				c = c + i - m
		return c

	def find_height(self, a, n, k):
		if n == 1:
			return -1 if k >= a[0] else a[0] - k
		l = min(a)
		r = max(a)
		while l <= r:
			m = (l + r) // 2
			c = self.fun(a, k, m)
			if c == k:
				return m
			elif c < k:
				r = m - 1
			elif c > k:
				l = m + 1
		return -1


class Solution:

	def isValid(self, trr, n, m):
		wood = 0
		for i in trr:
			if i > m:
				wood += i - m
		return wood

	def find_height(self, tree, n, k):
		s = 0
		e = max(tree)
		while s <= e:
			m = s + (e - s) // 2
			wood = self.isValid(tree, n, m)
			if wood == k:
				return m
			elif wood > k:
				s = m + 1
			else:
				e = m - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		small = 0
		high = tree[n - 1]
		while small <= high:
			cut = 0
			mid = (high + small) // 2
			for i in range(n):
				if tree[i] > mid:
					cut += tree[i] - mid
			if cut == k:
				return mid
			elif cut < k:
				high = mid - 1
			else:
				small = mid + 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tot = sum(tree)
		tree.sort()

		def count(H):
			count = 0
			for ht in tree[::-1]:
				if ht >= H:
					count += ht - H
				else:
					break
			return count
		(l, r) = (0, max(tree))
		while l <= r:
			mid = int(l + (r - l) / 2)
			if count(mid) < k:
				r = mid - 1
			elif count(mid) > k:
				l = mid + 1
			else:
				return mid
		return -1


class Solution:

	def isValid(self, tree, n, k, h):
		totalHeight = 0
		for i in range(n):
			x = tree[i] - h
			if x > 0:
				totalHeight += x
		if totalHeight >= k:
			return True
		return False

	def find_height(self, tree, n, k):
		start = 0
		end = max(tree)
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if self.isValid(tree, n, k, mid):
				res = mid
				start = mid + 1
			else:
				end = mid - 1
		if res != -1:
			t = 0
			for ele in tree:
				x = ele - res
				if x > 0:
					t += x
			if t == k:
				return res
			return -1
		else:
			return res


class Solution:

	def find_height(self, tree, n, k):
		total = sum(tree)
		if k > total:
			return -1
		tree.sort()
		temp = 0
		for i in range(len(tree)):
			temp += tree[i]
			flag = total - temp - tree[i] * (n - 1 - i)
			if flag == k:
				return tree[i]
			elif flag > k:
				continue
			else:
				if i > 0:
					low = tree[i - 1] + 1
					high = tree[i]
				else:
					low = 0
					high = tree[0]
				temp -= tree[i]
				while low <= high:
					mid = (low + high) // 2
					flag = total - temp - mid - (n - 1 - i) * mid
					if flag == k:
						return mid
					elif flag < k:
						high = mid - 1
					else:
						low = mid + 1
				return -1


class Solution:

	def calculate_tree_cost(self, arr, h):
		cost = 0
		for e in arr:
			if e > h:
				cost += e - h
		return cost

	def find_height(self, tree, n, k):
		l = 0
		h = max(tree)
		while l <= h:
			m = (l + h) // 2
			cost = self.calculate_tree_cost(tree, m)
			if cost == k:
				return m
			if cost > k:
				l = m + 1
			else:
				h = m - 1
		return -1


class Solution:

	def find_height(self, tree, n, k):
		tree.sort()
		low = 0
		high = tree[n - 1]
		while high >= low:
			mid = (low + high) // 2
			value = 0
			for item in tree:
				if item > mid:
					value += item - mid
			if value > k:
				low = mid + 1
			else:
				high = mid - 1
			if value == k:
				return mid
		return -1


class Solution:

	def find_height(self, trees, n, target_rest):
		lo = 0
		hi = max(trees)
		while lo + 1 < hi:
			cut = (lo + hi) // 2
			rest = i = 0
			while i < n and rest <= target_rest:
				rest += max(0, trees[i] - cut)
				i += 1
			if rest < target_rest:
				hi = cut
			elif rest == target_rest:
				return cut
			else:
				lo = cut + 1
		rest = sum([max(0, tree - lo) for tree in trees])
		return lo if rest == target_rest else -1


class Solution:

	def find_height(self, trees, n, target_rest):
		lo = 0
		hi = max(trees)
		while lo + 1 < hi:
			cut = (lo + hi) // 2
			rest = 0
			for tree in trees:
				rest += max(0, tree - cut)
				if rest > target_rest:
					lo = cut + 1
					break
			if rest == target_rest:
				return cut
			if rest < target_rest:
				hi = cut
		rest = 0
		for tree in trees:
			rest += max(0, tree - lo)
			if rest > target_rest:
				return -1
		return lo if rest == target_rest else -1


class Solution:

	def find_height(self, trees, n, target_rest):
		trees.sort(reverse=True)
		hi = len(trees)
		lo = 0
		while lo + 1 < hi:
			mid = (lo + hi) // 2
			rest = i = 0
			while i < mid and rest <= target_rest:
				rest += trees[i] - trees[mid]
				i += 1
			if rest > target_rest:
				hi = mid
			else:
				lo = mid
		rest = sum([trees[i] - trees[lo] for i in range(lo)])
		add = target_rest - rest
		return -1 if add % hi else trees[lo] - add // hi


class Solution:

	def find_height(self, trees, n, target_rest):
		trees.sort(reverse=True)
		i = len(trees) - 1
		rest = sum(trees)
		for cut in range(1, trees[0]):
			while trees[i] < cut:
				i -= 1
			rest -= i + 1
			if rest <= target_rest:
				break
		return cut if rest == target_rest else -1


class Solution:

	def find_height(self, tree, n, k):
		tree = sorted(tree)
		min_h = 0
		max_h = tree[n - 1]
		while min_h <= max_h:
			wood = 0
			height = min_h + (max_h - min_h) // 2
			for i in range(n):
				if tree[i] > height:
					wood += tree[i] - height
			if wood == k:
				return height
			elif wood > k:
				min_h = height + 1
			else:
				max_h = height - 1
		return -1


def solve(mid, A, N):
	amt = 0
	for i in range(N - 1, -1, -1):
		if A[i] <= mid:
			break
		amt += max(A[i] - mid, 0)
	return amt

class Solution:

	def find_height(self, tree, n, k):
		l = 0
		r = max(tree)
		tree.sort()
		while l <= r:
			mid = l + r >> 1
			amt = solve(mid, tree, n)
			if amt == k:
				return mid
			if amt < k:
				r = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def find_height(self, trees, n, target_rest):
		trees.sort(reverse=True)
		trees.append(0)
		lo = 0
		hi = len(trees)
		while lo + 1 < hi:
			mid = (lo + hi) // 2
			rest = 0
			for i in range(mid):
				rest += trees[i] - trees[mid]
				if rest > target_rest:
					hi = mid
					break
			if rest <= target_rest:
				lo = mid
		rest = sum([trees[i] - trees[lo] for i in range(lo)])
		dif = target_rest - rest
		return -1 if dif % (lo + 1) else trees[lo] - dif // (lo + 1)


class Solution:

	def find_height(self, tree, n, k):

		def getSum(tree, k):
			sum = 0
			for i in tree:
				if k > i:
					continue
				else:
					sum += i - k
			return sum
		(l, r) = (0, max(tree))
		while l <= r:
			mid = (l + r) // 2
			sum = getSum(tree, mid)
			if sum == k:
				return mid
			elif sum < k:
				r = mid - 1
			else:
				l = mid + 1
		return -1