Given an unsorted array Arr of size N. Find the minimum number of removals required such that twice of minimum element in the array is greater than or equal to the maximum in the array.
Example 1:
Input:
N = 9
Arr[] = {4,5,100,9,10,11,12,15,200}
Output: 4
Explanation: In the given array 4 elements 
4, 5, 200 and 100 are removed from the
array to make the array such that
2*minimum >= max (2*9 > 15).
Example 2:
Input:
N = 4
Arr[] = {4,7,5,6}
Output: 0
Explanation: We don't need to remove any
element as  4*2 > 7 (Note that min = 4,
max = 7).
Your Task:
You don't need to read input or print anything. Your task is to complete the function minRemoval() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{7}
1 ≤ Arr_{i} ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3
class Solution:

	def minRemoval(self,arr, n):
		# code here

Solutions:
import bisect

class Solution:

	def minRemoval(self, a, n):
		ans = 99999
		a.sort()
		if 2 * a[0] >= a[n - 1]:
			return 0
		for i in range(n):
			temp = 2 * a[i]
			p = bisect.bisect_right(a, temp)
			ans = min(ans, n - p + i)
		return ans


class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		c = 0
		sub = 0
		for i in range(n - 1):
			l = i
			h = n - 1
			ans = -1
			while l <= h:
				mid = (l + h) // 2
				if 2 * arr[i] >= arr[mid]:
					ans = mid
					l = mid + 1
				else:
					h = mid - 1
			if ans != -1:
				sub = max(sub, ans - i + 1)
		return n - sub


from bisect import bisect_right as upper
import sys

class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		ans = sys.maxsize
		for i in range(0, n):
			val = 2 * arr[i]
			idx = upper(arr, val)
			mindelete = n - idx + i
			ans = min(ans, mindelete)
		return ans


class Solution:

	def minRemoval(self, arr, n):
		import bisect
		ans = float('inf')
		arr.sort()
		if 2 * arr[0] >= arr[n - 1]:
			return 0
		for i in range(n):
			temp = 2 * arr[i]
			p = bisect.bisect_right(arr, temp)
			ans = min(ans, n - p + i)
		return ans


import bisect

class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		return n - max([bisect.bisect(arr, arr[i] * 2) - i for i in range(n)])


class Solution:

	def search(self, arr, low, high, target):
		while low <= high:
			mid = low + (high - low) // 2
			if target >= arr[mid]:
				low = mid + 1
			else:
				high = mid - 1
		return low

	def minRemoval(self, arr, n):
		arr.sort()
		min_count = 123456789
		for i in range(n):
			res = self.search(arr, i + 1, n - 1, 2 * arr[i])
			min_count = min(min_count, i + n - res)
		return min_count


class Solution:

	def minRemoval(self, arr, n):
		from bisect import bisect_right
		arrs = sorted(arr)
		if 2 * arrs[0] > arrs[-1]:
			return 0
		ans = n + 1
		for i in range(n):
			i_ind = bisect_right(arrs, arrs[i] * 2)
			ans = min(ans, n - i_ind + i)
		return ans


class Solution:

	def binarysearch(self, ele, arr, start, n):
		i = start
		j = n - 1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] > ele:
				j = mid - 1
			else:
				i = mid + 1
		return j

	def minRemoval(self, arr, n):
		arr.sort()
		res = 100000000
		for i in range(n):
			idx = self.binarysearch(arr[i] * 2, arr, i, n)
			res = min(res, n - (idx - i + 1))
		return res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.minRemoval(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		res = 0
		for i in range(n - 1):
			l = i
			r = n - 1
			ans = -1
			while l <= r:
				mid = (l + r) // 2
				if arr[i] * 2 >= arr[mid]:
					ans = mid
					l = mid + 1
				else:
					r = mid - 1
			if ans != -1:
				res = max(res, ans - i + 1)
		return n - res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.minRemoval(arr, n)
		print(ans)
		tc -= 1


import bisect

class Solution:

	def minRemoval(self, a, n):
		ans = 99999
		a.sort()
		if 2 * a[0] >= a[n - 1]:
			return 0
		for i in range(n):
			temp = 2 * a[i]
			p = bisect.bisect_right(a, temp)
			ans = min(ans, n - p + i)
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.minRemoval(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def minRemoval(self, arr, n):
		arr.sort()

		def binary(arr, val):
			i = 0
			j = len(arr) - 1
			while i < j:
				mid = (i + j + 1) // 2
				if arr[mid] <= val:
					i = mid
				else:
					j = mid - 1
			return i
		ans = -1
		for i in range(n):
			pos = binary(arr, 2 * arr[i])
			ans = max(ans, pos + 1 - i)
		return n - ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.minRemoval(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		if 2 * arr[0] >= arr[-1]:
			return 0

		def find(l, r, val):
			while l < r:
				mid = l + (r - l) // 2
				if val >= arr[mid]:
					l = mid + 1
				else:
					r = mid
			return l
		ans = 10 ** 9
		for i in range(n):
			index = find(i, n, 2 * arr[i])
			ans = min(ans, n - index + i)
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.minRemoval(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def minRemoval(self, l, n):
		l.sort()
		a = 0
		r = 0
		d = 0
		for i in range(n):
			if l[i] > 2 * l[a]:
				d = 1
				break
		if i == n - 1 and d != 1:
			return 0
		b = i - 1
		maxi = b - a + 1
		a += 1
		while n - a > maxi:
			if b + 1 < n:
				if l[b + 1] <= 2 * l[a]:
					b += 1
				else:
					a += 1
				maxi = max(maxi, b - a + 1)
			elif 2 * l[a + 1] >= l[b]:
				a += 1
				maxi = max(maxi, b - a + 1)
		return n - maxi


import bisect

class Solution:

	def minRemoval(self, arr, n):
		ans = float('inf')
		arr.sort()
		for i in range(n):
			j = bisect.bisect_right(arr, 2 * arr[i], i + 1, n)
			ans = min(ans, n - j + i)
		return ans


class Solution:

	def minRemoval(self, arr, n):
		ans = float('inf')
		arr.sort()
		for i in range(n):
			j = solve(arr, n, i)
			ans = min(ans, n - j - 1 + i)
		return ans

def solve(arr, n, i):
	low = i + 1
	high = n - 1
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		if 2 * arr[i] >= arr[mid]:
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	return ans


class Solution:

	def minRemoval(self, array, n):
		if n <= 1:
			return 0
		array.sort()
		i = 0
		maxLen = 0
		for j in range(i + 1, n):
			if arr[i] * 2 >= arr[j]:
				maxLen = max(maxLen, j - i + 1)
			else:
				i += 1
		return n - maxLen


import sys
import bisect

class Solution:

	def minRemoval(self, arr, n):
		arr.sort()
		if 2 * arr[0] > arr[-1]:
			return 0
		mincount = sys.maxsize
		for i in range(n):
			index = bisect.bisect_right(arr, 2 * arr[i], lo=0, hi=n)
			mincount = min(mincount, n - 1 - index + i + 1)
		return mincount


class Solution:

	def minRemoval(self, arr, n):
		if n == 1:
			return 0
		arr.sort()
		i = 0
		j = i + 1
		res = 1000000007
		while j < n:
			while j < n:
				if 2 * arr[i] >= arr[j]:
					j += 1
				else:
					break
			res = min(res, n - (j - i))
			i += 1
		return res