Given heights h[] of N towers, the task is to bring every tower to the same height by either adding or removing blocks in a tower. Every addition or removal operation costs cost[] a particular value for the respective tower. Find out the Minimum cost to Equalize the Towers.
Example 1:
Input: N = 3, h[] = {1, 2, 3} 
cost[] = {10, 100, 1000}
Output: 120
Explanation: The heights can be equalized 
by either "Removing one block from 3 and 
adding one in 1" or "Adding two blocks in 
1 and adding one in 2". Since the cost 
of operation in tower 3 is 1000, the first 
process would yield 1010 while the second 
one yields 120. Since the second process 
yields the lowest cost of operation, it is 
the required output.
 
Example 2:
Input: N = 5, h[] = {9, 12, 18, 3, 10} 
cost[] = {100, 110, 150, 25, 99}
Output: 1623 
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function Bsearch() that takes integer N, array H, and array Cost as parameters and returns the minimum cost required to equalize the towers.
 
Expected Time Complexity: O(NlogN). 
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: class Solution:

    def Bsearch(self, n, h, cost):

        # Your code goes here

Solutions:
class Solution:

	def Bsearch(self, n, h, cost):
		l = 0
		r = 0
		for e in h:
			r = max(r, e)
		for e in h:
			l = min(l, e)
		lc = 0
		pc = 0
		ans = 0
		while l <= r:
			mid = (l + r) // 2
			lc = self.total_cost(mid - 1, h, cost)
			pc = self.total_cost(mid, h, cost)
			if lc >= pc:
				ans = pc
				l = mid + 1
			else:
				r = mid - 1
		return ans

	def total_cost(self, mid, h, Cost):
		total_cost = 0
		for i in range(len(h)):
			total_cost += abs(mid - h[i]) * Cost[i]
		return total_cost


class Solution:

	def Bsearch(self, n, h, cost):
		if len(set(h)) == 1:
			return 0
		arr = [(h[i], cost[i]) for i in range(n)]
		arr.sort()
		summa1 = sum((abs(arr[j][0] - arr[0][0]) * arr[j][1] for j in range(n)))
		summa2 = sum((abs(arr[j][0] - arr[1][0]) * arr[j][1] for j in range(n)))
		if summa1 < summa2:
			return summa1
		summa1 = sum((abs(arr[j][0] - arr[-1][0]) * arr[j][1] for j in range(n)))
		summa2 = sum((abs(arr[j][0] - arr[-2][0]) * arr[j][1] for j in range(n)))
		if summa1 < summa2:
			return summa1
		return self.helper(0, n, arr, n)

	def helper(self, low, high, arr, n):
		summa1 = sum((abs(arr[j][0] - arr[low][0]) * arr[j][1] for j in range(n)))
		summa2 = sum((abs(arr[j][0] - arr[high - 1][0]) * arr[j][1] for j in range(n)))
		while high - low > 1:
			i = (low + high) // 2
			summa1 = sum((abs(arr[j][0] - arr[i][0]) * arr[j][1] for j in range(n)))
			summa2 = sum((abs(arr[j][0] - arr[i + 1][0]) * arr[j][1] for j in range(n)))
			if summa1 > summa2:
				low = i
			elif summa1 < summa2:
				high = i
			else:
				return min(self.helper(low, i, arr, n), self.helper(i, high, arr, n))
		return min(summa1, summa2)


class Solution:

	def check(self, n, h, cost, mid):
		ans = 0
		for i in range(n):
			ans += abs(h[i] - mid) * cost[i]
		return ans

	def Bsearch(self, n, h, cost):
		ans = 9999999999
		lo = 0
		hi = 1000000.0
		mid = (lo + hi) // 2
		while lo <= hi:
			cs = self.check(n, h, cost, mid + 1)
			cm = self.check(n, h, cost, mid)
			ce = self.check(n, h, cost, mid - 1)
			if ce >= cm and cm <= cs:
				return int(cm)
			elif ce < cm:
				hi = mid - 1
			else:
				lo = mid + 1
			mid = (lo + hi) // 2
			ans = max(ans, cm)
		return int(ans)


class Solution:

	def getcost(self, cost, h, target):
		total_cost = 0
		for i in range(len(h)):
			l = abs(h[i] - target)
			total_cost += l * cost[i]
		return total_cost

	def Bsearch(self, n, h, cost):
		low = min(h)
		high = max(h)
		while low <= high:
			mid = low + (high - low) // 2
			cost_mid = self.getcost(cost, h, mid)
			cost_left = self.getcost(cost, h, mid - 1)
			cost_right = self.getcost(cost, h, mid + 1)
			if cost_mid <= cost_left and cost_mid <= cost_right:
				return cost_mid
			elif cost_mid < cost_left:
				low = mid + 1
			else:
				high = mid - 1


import sys

class Solution:

	def costOfOperation(self, n, h, cost, eq_h):
		c = 0
		for i in range(0, n, 1):
			c += abs(h[i] - eq_h) * cost[i]
		return c

	def Bsearch(self, n, h, cost):
		max_h = h[0]
		for i in range(len(h)):
			if h[i] > max_h:
				max_h = h[i]
		ans = sys.maxsize
		high = 1 + max_h
		low = 0
		while high > low:
			mid = (low + high) // 2
			if mid > 0:
				bm = self.costOfOperation(n, h, cost, mid - 1)
			else:
				bm = sys.maxsize
			m = self.costOfOperation(n, h, cost, mid)
			am = self.costOfOperation(n, h, cost, mid + 1)
			if ans == m:
				break
			ans = min(ans, m)
			if bm <= m:
				high = mid
			elif am <= m:
				low = mid + 1
			else:
				return m
		return ans


class Solution:

	def cost2(self, arr, c, h):
		cos = 0
		for i in range(len(arr)):
			cos += c[i] * abs(arr[i] - h)
		return cos

	def binarysearch(self, arr, c, l, r):
		if l <= r:
			mid = (l + r) // 2
			bm = 100000000.0
			am = 100000000.0
			if mid > 0:
				bm = self.cost2(arr, c, mid - 1)
			mm = self.cost2(arr, c, mid)
			am = self.cost2(arr, c, mid + 1)
			if mm <= am:
				return self.binarysearch(arr, c, l, mid - 1)
			else:
				return self.binarysearch(arr, c, mid + 1, r)
		return self.cost2(arr, c, l)

	def Bsearch(self, n, h, cost):
		return self.binarysearch(h, cost, 0, max(h))


def solve(H, cost, mid):
	ans = 0
	for i in range(len(H)):
		d = abs(mid - H[i])
		ans += cost[i] * d
	return ans

class Solution:

	def Bsearch(self, N, H, cost):
		l = min(H)
		r = max(H)
		ans = 1000000000.0
		while l <= r:
			mid = l + r >> 1
			c = solve(H, cost, mid)
			prev = solve(H, cost, mid - 1)
			if c <= prev:
				ans = c
				l = mid + 1
			else:
				ans = prev
				r = mid - 1
		return ans


class Solution:

	def isValid(self, n, h, cost, midHeight):
		totalCost = 0
		for i in range(n):
			totalCost += abs(h[i] - midHeight) * cost[i]
		return totalCost

	def Bsearch(self, n, h, cost):
		start = 0
		end = 10000000000.0
		while start <= end:
			mid = (start + end) // 2
			midCost = self.isValid(n, h, cost, mid)
			midCostBelow = self.isValid(n, h, cost, mid - 1)
			midCostAbove = self.isValid(n, h, cost, mid + 1)
			if midCostBelow >= midCost and midCost <= midCostAbove:
				return int(midCost)
			if midCostBelow < midCost:
				end = mid - 1
			elif midCostAbove < midCost:
				start = mid + 1


class Solution:

	def totalCost(self, mid, h, cost):
		totalcost = 0
		for i in range(len(h)):
			length = abs(mid - h[i])
			totalcost += length * cost[i]
		return totalcost

	def Bsearch(self, n, h, cost):
		low = min(h)
		high = max(h)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			left = self.totalCost(mid - 1, h, cost)
			m = self.totalCost(mid, h, cost)
			right = self.totalCost(mid + 1, h, cost)
			if m <= left and m <= right:
				return m
			elif m < left:
				low = mid + 1
			elif m < right:
				high = mid - 1
		return -1


import sys

class Solution:

	def Bsearch(self, n, h, cost):

		def cost_of(val):
			return sum([abs(hi - val) * ci for (hi, ci) in zip(h, cost)])
		(l, r) = (0, max(h))
		ans = sys.maxsize
		while l <= r:
			mid = l + r >> 1
			cost_at_mid = cost_of(mid)
			cost_at_lower = cost_of(mid - 1) if mid > 0 else sys.maxsize
			cost_at_higher = cost_of(mid + 1)
			ans = min(ans, cost_at_mid, cost_at_lower, cost_at_higher)
			if cost_at_lower >= cost_at_mid:
				l = mid + 1
			elif cost_at_higher >= cost_at_mid:
				r = mid - 1
			else:
				return cost_at_mid
		return ans


class Solution:

	def get_cost(self, new_height, h, cost):
		res = 0
		for (hi, ci) in zip(h, cost):
			res += abs(hi - new_height) * ci
		return res

	def Bsearch(self, n, h, cost):
		(l, r) = (min(h), max(h))
		min_cost = float('inf')
		while r - l > 1:
			mid = (l + r) // 2
			bm_cost = self.get_cost(mid - 1, h, cost)
			am_cost = self.get_cost(mid + 1, h, cost)
			mcost = self.get_cost(mid, h, cost)
			min_cost = min(min_cost, mcost)
			if mcost <= bm_cost and mcost <= am_cost:
				return mcost
			if mcost >= am_cost:
				l = mid
			elif mcost >= bm_cost:
				r = mid
		return min(min_cost, self.get_cost(l, h, cost), self.get_cost(r, h, cost))


class Solution:

	def calc(self, h, cost, value, maxi, n):
		import sys
		if value < 1 or value > maxi:
			return sys.maxsize
		ans = 0
		for i in range(n):
			ans += abs(h[i] - value) * cost[i]
		return ans

	def Bsearch(self, n, h, cost):
		low = 1
		maxi = max(h)
		high = maxi
		import sys
		ans = sys.maxsize
		while low <= high:
			mid = low + (high - low) // 2
			mid_ans = self.calc(h, cost, mid, maxi, n)
			left_ans = self.calc(h, cost, mid - 1, maxi, n)
			right_ans = self.calc(h, cost, mid + 1, maxi, n)
			if mid_ans < left_ans and mid_ans < right_ans:
				ans = min(ans, mid_ans)
				return ans
			elif left_ans < mid_ans:
				ans = min(ans, left_ans)
				high = mid - 1
			else:
				ans = min(ans, right_ans)
				low = mid + 1
		return ans


class Solution:

	def Bsearch(self, n, h, cost):
		lo = 0
		hi = max(h)
		res = -1
		while lo <= hi:
			m = lo + (hi - lo) // 2

			def minheight(x):
				min_height = x
				i = 0
				mycost = 0
				while i < n:
					if h[i] < min_height or h[i] > min_height:
						mycost += cost[i] * abs(min_height - h[i])
					i += 1
				return mycost
			y = minheight(m)
			if minheight(m + 1) > y:
				res = y
				hi = m - 1
			else:
				lo = m + 1
		return res


class Solution:

	def Bsearch(self, n, h, cost):
		start = 0
		end = 1000000.0
		while end >= start:
			mid = start + (end - start) // 2
			curr = self.costofequalisation(n, h, cost, mid)
			next = self.costofequalisation(n, h, cost, mid + 1)
			prev = self.costofequalisation(n, h, cost, mid - 1)
			if next >= curr and prev >= curr:
				return int(curr)
			if curr == 0:
				return -1
			elif curr < next:
				end = mid - 1
			elif curr < prev:
				start = mid + 1
		return -1

	def costofequalisation(self, n, h, cost, equalheight):
		sum = 0
		for i in range(n):
			sum += abs(equalheight - h[i]) * cost[i]
		return sum


class Solution:

	def check(self, t, n, h, cost):
		ans = 0
		for i in range(n):
			ans += abs(h[i] - t) * cost[i]
		return ans

	def Bsearch(self, n, h, cost):
		lo = min(h)
		hi = max(h)
		ans = 100000000000
		while lo <= hi:
			mid = (lo + hi) // 2
			costmb = self.check(mid - 1, n, h, cost)
			costm = self.check(mid, n, h, cost)
			costma = self.check(mid + 1, n, h, cost)
			if costmb > costm and costm < costma:
				return costm
			elif costmb < costm:
				hi = mid - 1
			else:
				lo = mid + 1
			ans = min(ans, costm)
		return ans


def check(h, cost, m):
	ans = 0
	for (x, c) in zip(h, cost):
		ans += abs(x - m) * c
	return ans

class Solution:

	def Bsearch(self, n, h, cost):
		(s, e) = (min(h), max(h))
		while s <= e:
			mid = s + (e - s) // 2
			m = check(h, cost, mid)
			p = check(h, cost, mid - 1)
			nx = check(h, cost, mid + 1)
			if m <= p and m <= nx:
				return m
			elif m < nx:
				e = mid - 1
			elif m < p:
				s = mid + 1
		return -1


class Solution:

	def Bsearch(self, n, h, cost):
		res = 0
		low = 0
		high = max(h)
		while low <= high:
			mid = low + (high - low) // 2
			res_x = self.getcost(h, cost, mid)
			res_x_plus_one = self.getcost(h, cost, mid + 1)
			res_x_minus_one = self.getcost(h, cost, mid - 1)
			if res_x_minus_one >= res_x and res_x <= res_x_plus_one:
				return res_x
			elif res_x_minus_one < res_x:
				high = mid - 1
			else:
				low = mid + 1

	def getcost(self, h, cost, pos):
		overallcost = 0
		for i in range(len(h)):
			overallcost += abs(h[i] - pos) * cost[i]
		return overallcost


class Solution:

	def findCost(self, h, cost, x):
		s = 0
		for i in range(len(h)):
			s += abs(h[i] - x) * cost[i]
		return s

	def Bsearch(self, n, h, cost):
		lo = min(h)
		hi = max(h)
		while lo <= hi:
			m = lo + hi >> 1
			cur = self.findCost(h, cost, m)
			nxt = self.findCost(h, cost, m + 1)
			prv = self.findCost(h, cost, m - 1)
			if cur == min(prv, nxt, cur):
				return cur
			elif cur < nxt:
				hi = m - 1
			elif cur < prv:
				lo = m + 1
		return -1