You are given an array Arr of size N containing non-negative integers. Your task is to choose the minimum number of elements such that their sum should be greater than the sum of the rest of the elements of the array.
Example 1:
Input:
N = 4 
Arr[] = {2, 17, 7, 3}
Output:
1
Explanation:
If we only select element 17, the sum of the
rest of the elements will be (2+3+7)=12.
So the answer will be 1.
Example 2:
Input:
N = 4
Arr = {20, 12, 18, 4}
Output:
2
Explanation:
If we select 12 and 18 from the array,
the sum will be (12+18) = 30 and the sum of
the rest of the elements will be (20+4) = 24.
So, the answer will be 2. We can also
select 20 and 18 as well.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minSubset() which takes the array Arr[] and its size N as inputs and returns the minimum number of elements to be selected.
 
Expected Time Complexity: O(N log N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1 <= Arr[i] <= 10^{9}
Array may contain duplicate elements.

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def minSubset(self, A,N):

Solutions:
class Solution:

	def minSubset(self, A, N):
		A = sorted(A)
		sum_val = sum(A)
		i = N - 1
		curr_sum = 0
		while i > -1 and curr_sum <= sum_val / 2:
			curr_sum += A[i]
			i -= 1
		return len(A) - i - 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		s = sum(A)
		sm = 0
		c = 0
		for i in range(N - 1, -1, -1):
			sm += A[i]
			a = s - sm
			c += 1
			if a < sm:
				return c


class Solution:

	def minSubset(self, A, N):
		s = sum(A)
		A.sort()
		i = N - 1
		d = 0
		while i >= 0:
			d += A[i]
			if d > s - d:
				return N - i
			i -= 1
		return N


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		left_sum = A[0]
		right_sum = sum(A[1:])
		left_cnt = 1
		for i in range(1, N):
			if left_sum > right_sum:
				break
			else:
				left_sum += A[i]
				right_sum -= A[i]
				left_cnt += 1
		return left_cnt


class Solution:

	def minSubset(self, A, N):
		A.sort()
		sumi = sum(A)
		i = N - 1
		curr_sum = 0
		while i >= 0:
			curr_sum += A[i]
			sumi -= A[i]
			if curr_sum > sumi:
				return N - i
			i -= 1
		return N


class Solution:

	def minSubset(self, A, N):
		count = 0
		A.sort()
		child = sum(A)
		parent = 0
		if N == 1:
			return 1
		for i in range(N - 1, -1, -1):
			if parent > child:
				return count
			else:
				parent = parent + A[i]
				child = child - A[i]
				count = count + 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		arr = []
		s = 0
		su = sum(A) // 2
		while s <= su:
			s += A[-1]
			arr.append(A.pop())
		return len(arr)


class Solution:

	def minSubset(self, A, N):
		s = sum(A)
		res = 0
		A.sort(reverse=True)
		for i in range(0, N):
			res += A[i]
			s -= A[i]
			if res > s:
				return i + 1
		return N


class Solution:

	def minSubset(self, A, N):
		A.sort()
		s1 = sum(A)
		s2 = 0
		ans = 0
		j = N - 1
		while True:
			s1 -= A[j]
			s2 += A[j]
			j -= 1
			ans += 1
			if s2 > s1:
				break
		return ans


class Solution:

	def minSubset(self, A, N):
		suma = 0
		for i in A:
			suma = suma + i
		A.sort(reverse=True)
		suma_2 = 0
		for i in range(N):
			suma_2 = suma_2 + A[i]
			suma = suma - A[i]
			if suma_2 > suma:
				return i + 1


class Solution:

	def minSubset(self, arr, n):
		arr.sort(reverse=True)
		i = count = 0
		sum_selected = arr[0]
		sum_rest = sum(arr[1:])
		if sum_selected > sum_rest:
			return 1
		while sum_selected <= sum_rest and i < n - 1:
			i += 1
			sum_selected += arr[i]
			sum_rest -= arr[i]
			count += 1
		return count + 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		sumi = sum(A)
		r = N - 1
		count = 0
		sub = 0
		while True:
			sub += A[r]
			sumi -= A[r]
			r -= 1
			count += 1
			if sub > sumi:
				return count
		return count


class Solution:

	def minSubset(self, A, N):
		A.sort()
		_sum = 0
		for index in range(N):
			_sum += A[index]
		aux_sum = 0
		count = 0
		for index in range(N - 1, -1, -1):
			aux_sum += A[index]
			_sum -= A[index]
			count += 1
			if aux_sum > _sum:
				return count
		return -1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		total = sum(A)
		sum2 = 0
		count = 0
		l = []
		for i in range(N - 1, -1, -1):
			sum2 += A[i]
			count += 1
			if sum2 > total - sum2:
				break
		return count


class Solution:

	def minSubset(self, A, N):
		total_sum = sum(A)
		A.sort(reverse=True)
		(left, right) = (1, N)
		while left <= right:
			mid = left + (right - left) // 2
			subset_sum = sum(A[:mid])
			if subset_sum > total_sum - subset_sum:
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution:

	def minSubset(self, arr, n):
		arr.sort()
		s1 = sum(arr)
		s2 = 0
		c = 0
		j = n - 1
		while True:
			s1 -= arr[j]
			s2 += arr[j]
			j -= 1
			c += 1
			if s2 > s1:
				break
		return c


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		i = c = 0
		S = A[0]
		R = sum(A[1:])
		if S > R:
			return 1
		else:
			while S <= R and i < N - 1:
				i += 1
				S = S + A[i]
				R = R - A[i]
				c += 1
		return c + 1


class Solution:

	def minSubset(self, A, N):
		if N == 1:
			return 1
		s1 = sum(A)
		s2 = 0
		A.sort()
		i = N - 1
		ans = 0
		while i >= 0:
			if s2 > s1:
				return ans
			else:
				s2 += A[i]
				s1 -= A[i]
				i -= 1
				ans += 1


import heapq

class Solution:

	def minSubset(self, A, N):
		sum1 = sum(A)
		A.sort(reverse=True)
		sum2 = 0
		count = 0
		for items in A:
			sum2 += items
			sum1 -= items
			count += 1
			if sum2 > sum1:
				break
		return count


class Solution:

	def minSubset(self, A, N):
		A = sorted(A)
		sum1 = sum(A)
		res = 0
		for i in range(N - 1, -1, -1):
			res += A[i]
			sum1 -= A[i]
			if res > sum1:
				return N - i
		return N


class Solution:

	def minSubset(self, A, N):
		A.sort()
		rem_sum = sum(A)
		sub_sum = 0
		c = 0
		for i in range(N - 1, -1, -1):
			rem_sum -= A[i]
			sub_sum += A[i]
			c += 1
			if sub_sum > rem_sum:
				return c


class Solution:

	def minSubset(self, A, N):
		A.sort()
		sm1 = 0
		sm = sum(A)
		for i in range(len(A) - 1, -1, -1):
			sm1 = sm1 + A[i]
			n = sm - sm1
			if sm1 > n:
				return len(A) - i


class Solution:

	def minSubset(self, A, N):
		(total_sum, sum) = (0, 0)
		for i in range(N):
			total_sum += A[i]
		count = 0
		A.sort()
		for i in range(N - 1, -1, -1):
			sum += A[i]
			total_sum -= A[i]
			count += 1
			if sum > total_sum:
				break
		return count


def smallest_subset_sum_greater_all_element(arr: [], n):
	arr = sorted(arr, reverse=True)
	total_sum = sum(arr)
	curr_sum = 0
	for i in range(0, n):
		if curr_sum > total_sum:
			return i
		curr_sum = curr_sum + arr[i]
		total_sum = total_sum - arr[i]
	return 1

class Solution:

	def minSubset(self, A, N):
		return smallest_subset_sum_greater_all_element(A, N)


class Solution:

	def minSubset(self, A, N):
		count = 0
		A.sort(reverse=True)
		sum1 = 0
		total = sum(A)
		for i in A:
			sum1 += i
			total -= i
			count += 1
			if sum1 > total:
				return count
		return 0


class Solution:

	def minSubset(self, A, N):
		A.sort()
		s = sum(A)
		cnt = 0
		val = 0
		for i in range(N - 1, -1, -1):
			val += A[i]
			cnt += 1
			if val > s - val:
				return cnt


class Solution:

	def minSubset(self, A, N):
		halfsum = 0
		for i in range(N):
			halfsum += A[i]
		halfsum = int(halfsum / 2)
		A.sort(reverse=True)
		res = 0
		currsum = 0
		for i in range(N):
			currsum += A[i]
			res += 1
			if currsum > halfsum:
				return res
		return res


class Solution:

	def minSubset(self, A, N):
		A.sort()
		sum_A = sum(A)
		sum_ele = 0
		count = 0
		j = N - 1
		while True:
			sum_A -= A[j]
			sum_ele += A[j]
			j -= 1
			count += 1
			if sum_ele > sum_A:
				break
		return count


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		sum_total = sum(A)
		sum_left = 0
		count = 0
		for i in A:
			sum_total -= i
			sum_left += i
			count += 1
			if sum_left > sum_total:
				return count


class Solution:

	def minSubset(self, A, N):
		rec = sum(A)
		A.sort()
		ac = 0
		cnt = 0
		for x in reversed(A):
			if ac > rec:
				break
			ac += x
			rec -= x
			cnt += 1
		return cnt


class Solution:

	def minSubset(self, A, N):
		A.sort()
		sumi = sum(A)
		newsum = 0
		c = 0
		for ele in A[::-1]:
			sumi = sumi - ele
			newsum = newsum + ele
			c = c + 1
			if sumi < newsum:
				return c


class Solution:

	def minSubset(self, A, N):
		A.sort()
		totalsum = sum(A)
		end = N - 1
		subsum = A[end]
		target = 1
		while end > 0:
			if subsum > totalsum - subsum:
				return target
			else:
				end -= 1
				subsum += A[end]
				target += 1
		return target


class Solution:

	def minSubset(self, arr, N):
		arr.sort(reverse=True)
		a = sum(arr)
		b = 0
		for i in range(len(arr)):
			a -= arr[i]
			b += arr[i]
			if b > a:
				return i + 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		total = 0
		subTotal = A[N - 1]
		for i in range(N - 1):
			total += A[i]
		j = N - 2
		while total >= subTotal:
			total -= A[j]
			subTotal += A[j]
			j -= 1
		return N - 1 - j


class Solution:

	def minSubset(self, A, N):
		if len(A) == 1:
			return 1
		A.sort()
		s = sum(A)
		s1 = 0
		k = 0
		for i in range(N - 1, 0, -1):
			s -= A[i]
			s1 += A[i]
			k += 1
			if s1 > s:
				return k
		return -1


class Solution:

	def minSubset(self, a, n):
		a.sort()
		s = sum(a)
		l = 0
		c = 0
		for i in range(n - 1, -1, -1):
			l = l + a[i]
			c = c + 1
			if l > s - l:
				return c


class Solution:

	def minSubset(self, arr, N):
		totalsum = 0
		for e in arr:
			totalsum += e
		arr = sorted(arr, reverse=True)
		res = 0
		cursum = 0
		for i in range(len(arr)):
			cursum += arr[i]
			res += 1
			if cursum > totalsum - cursum:
				return res
		return res


class Solution:

	def minSubset(self, A, N):
		sum = 0
		checksum = 0
		cnt = 0
		for i in range(N):
			sum += A[i]
		A.sort(reverse=True)
		for i in range(N):
			checksum += A[i]
			sum -= A[i]
			if checksum > sum:
				return i + 1
		return -1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		total = sum(A)
		ans = 0
		delete_total = 0
		for i in range(N - 1, -1, -1):
			delete_total += A[i]
			total -= A[i]
			ans += 1
			if delete_total > total:
				return ans
		return ans


class Solution:

	def minSubset(self, a, N):
		a.sort(reverse=True)
		sum1 = sum(a)
		l = 0
		count = 0
		for i in a:
			l += i
			sum1 -= i
			count += 1
			if l > sum1:
				return count


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		res = 0
		sum1 = sum(A)
		halfsum = int(sum1 / 2)
		curr_sum = 0
		for i in range(len(A)):
			curr_sum += A[i]
			res += 1
			if curr_sum > halfsum:
				return res
		return -1


class Solution:

	def quicksort(self, arr, l, h):
		if l < h:
			p = self.partition(arr, l, h)
			self.quicksort(arr, l, p - 1)
			self.quicksort(arr, p + 1, h)

	def partition(self, arr, l, h):
		pivot = arr[h]
		i = l - 1
		for j in range(l, h):
			if arr[j] <= pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[h]) = (arr[h], arr[i + 1])
		return i + 1

	def minSubset(self, A, N):
		self.quicksort(A, 0, N - 1)
		sum1 = 0
		for i in A:
			sum1 += i
		i = 0
		j = N - 1
		sum2 = 0
		while 0 <= j:
			sum1 -= A[j]
			sum2 += A[j]
			if sum1 < sum2:
				return N - j
			j -= 1
		return N


class Solution:

	def minSubset(self, array, N):
		array = sorted(array, reverse=True)
		total_sum = sum(array)
		counter = 1
		prefix = 0
		for i in range(N):
			prefix += array[i]
			if total_sum - prefix < prefix:
				return counter
			else:
				counter += 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		if N <= 2:
			return 1
		sum1 = sum(A)
		sum2 = 0
		for i in range(N):
			sum2 += A[N - i - 1]
			sum1 -= A[N - i - 1]
			if sum1 < sum2:
				return i + 1


class Solution:

	def minSubset(self, a, N):
		a.sort()
		s = sum(a)
		c = 0
		ans = 0
		for i in range(N - 1, -1, -1):
			if s - a[i] < ans + a[i]:
				c += 1
				return c
			else:
				s = s - a[i]
				ans += a[i]
				c += 1
		return N


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		ts = sum(A)
		ss = 0
		sc = 0
		for i in range(len(A)):
			ss += A[i]
			sc += 1
			if ss > ts - ss:
				return sc
		return -1


class Solution:

	def minSubset(self, A, N):
		fsum = sum(A)
		hsum = sum(A) / 2
		A.sort(reverse=True)
		currsum = 0
		for i in range(N):
			currsum += A[i]
			if currsum > hsum:
				return i + 1


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		su = 0
		sums = sum(A)
		c = 0
		for i in range(N):
			if su <= sums:
				su += A[i]
				sums = sums - A[i]
				c += 1
		return c


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		s = sum(A)
		(c, ss) = (0, 0)
		for i in range(N):
			ss += A[i]
			if 2 * ss > s:
				return i + 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		s = sum(A)
		S = 0
		ans = 0
		i = N - 1
		while s >= S:
			s -= A[i]
			S += A[i]
			i -= 1
			ans += 1
		return ans


class Solution:

	def minSubset(self, arr, n):
		arr.sort()
		total = sum(arr)
		i = n - 1
		s = 0
		while i >= 0:
			s += arr[i]
			total -= arr[i]
			if s > total:
				return n - i
			i -= 1
		return n


class Solution:

	def minSubset(self, A, N):
		A.sort()
		mi = 999999
		su = sum(A)
		i = 0
		j = 0
		p = 0
		while j < N:
			p += A[j]
			while p > su - p:
				mi = min(mi, j - i + 1)
				p -= A[i]
				i += 1
			j += 1
		return mi


class Solution:

	def minSubset(self, A, N):
		sort = sorted(A)
		total = sum(A)
		cursum = 0
		for i in range(len(A) - 1, 0, -1):
			cursum += sort[i]
			if cursum > total - cursum:
				return len(A) - i
		return 1


class Solution:

	def minSubset(self, A, N):
		A = sorted(A, reverse=True)
		sm = 0
		for a in A:
			sm += a
		temp = 0
		count = 0
		for a in A:
			temp += a
			count += 1
			x = sm - temp
			if temp > x:
				return count


from itertools import combinations

class Solution:

	def minSubset(self, A, N):
		A = sorted(A)[::-1]
		sums = sum(A)
		su = 0
		for i in range(N):
			su += A[i]
			sums = sums - A[i]
			if su > sums:
				return i + 1


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		summ = sum(A)
		maxsum = 0
		i = 0
		while summ >= maxsum and i < N:
			summ -= A[i]
			maxsum += A[i]
			i += 1
		return i


class Solution:

	def minSubset(self, a, n):
		a.sort()
		count = 0
		sumofsubset = 0
		totalsum = sum(a)
		for i in range(n - 1, -1, -1):
			sumofsubset += a[i]
			totalsum -= a[i]
			count += 1
			if sumofsubset > totalsum:
				return count
		return count


class Solution:

	def minSubset(self, arr, n):
		halfSum = 0
		for i in range(n):
			halfSum = halfSum + arr[i]
		halfSum = int(halfSum / 2)
		arr.sort(reverse=True)
		res = 0
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			res += 1
			if curr_sum > halfSum:
				return res
		return res


class Solution:

	def minSubset(self, A, N):
		s = sum(A)
		t = 0
		c = 0
		A.sort(reverse=True)
		for i in A:
			t += i
			s -= i
			c += 1
			if t > s:
				return c
		return -1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		summ = sum(A)
		curSum = 0
		count = 0
		for i in range(N - 1, -1, -1):
			curSum += A[i]
			summ -= A[i]
			count += 1
			if curSum > summ:
				return count


class Solution:

	def minSubset(self, arr, n):
		arr.sort(reverse=True)
		s = 0
		sm = sum(arr)
		ans = sm
		c = 0
		for i in range(len(arr)):
			s += arr[i]
			c += 1
			if s > sm - s:
				ans = c
				break
		return ans


class Solution:

	def minSubset(self, A, N):
		A.sort()
		right = 0
		for i in A:
			right += i
		left = 0
		count = N
		for i in A:
			left += i
			right -= i
			if right > left:
				count -= 1
			else:
				break
		return count


class Solution:

	def minSubset(self, A, N):
		A.sort()
		A = A[::-1]
		s = sum(A)
		t = 0
		for i in range(N // 2 + 1):
			t += A[i]
			if t > s - t:
				return i + 1
		return N


class Solution:

	def minSubset(self, arr, N):
		arr.sort(reverse=True)
		total_sum = 0
		length = len(arr)
		i = 0
		while i < length:
			total_sum += arr[i]
			i += 1
		current_sum = 0
		num_of_elements = 0
		i = 0
		while i < length:
			current_sum += arr[i]
			num_of_elements += 1
			if current_sum > total_sum - current_sum:
				break
			i += 1
		return num_of_elements


class Solution:

	def minSubset(self, arr, N):
		arr.sort(reverse=True)
		total_sum = 0
		for element in arr:
			total_sum += element
		current_sum = 0
		num_of_elements = 0
		for element in arr:
			current_sum += element
			num_of_elements += 1
			if current_sum > total_sum - current_sum:
				break
		return num_of_elements


class Solution:

	def minSubset(self, A, N):
		A.sort()
		A.reverse()
		total_sum = sum(A)
		temp = 0
		for i in range(N):
			temp += A[i]
			total_sum -= A[i]
			if temp > total_sum:
				return i + 1
		return n


class Solution:

	def minSubset(self, A, N):
		s = sum(A)
		A.sort(reverse=True)
		i = 0
		count = 0
		l = []
		temp = 0
		while i < N:
			temp += A[i]
			s = s - A[i]
			count += 1
			if temp > s:
				return count
			i = i + 1


class Solution:

	def minSubset(self, a, n):
		suma = sum(a)
		a.sort()
		csum = 0
		for i in range(n - 1, -1, -1):
			csum += a[i]
			rem = suma - csum
			if csum > rem:
				return n - i


class Solution:

	def minSubset(self, arr, n):
		halfsum = 0
		for i in range(n):
			halfsum = halfsum + arr[i]
		halfsum = int(halfsum / 2)
		arr.sort(reverse=True)
		res = 0
		current_sum = 0
		for i in range(n):
			current_sum += arr[i]
			res += 1
			if current_sum > halfsum:
				return res
		return res


class Solution:

	def minSubset(self, A, N):
		targetSum = sum(A) / 2
		A.sort(reverse=True)
		summ = 0
		for i in range(N):
			summ += A[i]
			if summ > targetSum:
				return i + 1


class Solution:

	def minSubset(self, A, N):
		A.sort()
		l = h = 0
		Sum = sum(A)
		sum1 = 0
		ans = N
		while h < N:
			while h < N and Sum >= sum1:
				sum1 += A[h]
				Sum -= A[h]
				h += 1
			while l < N and Sum < sum1:
				sum1 -= A[l]
				Sum += A[l]
				l += 1
			ans = min(ans, h - l + 1)
		return ans


class Solution:

	def minSubset(self, A, N):
		A.sort(reverse=True)
		cur_sum = 0
		all_sum = 0
		num_ele = 0
		for i in A:
			all_sum += i
		for i in A:
			cur_sum += i
			all_sum -= i
			num_ele += 1
			if cur_sum > all_sum:
				return num_ele


class Solution:

	def minSubset(self, A, N):
		sum1 = sum(A)
		A.sort()
		res = 0
		resum = 0
		for i in range(N - 1, -1, -1):
			sum1 = sum1 - A[i]
			resum = resum + A[i]
			res = res + 1
			if resum > sum1:
				break
		return res


class Solution:

	def minSubset(self, A, N):
		A = sorted(A, reverse=True)
		total_sum = sum(A)
		min_sum = 0
		i = 0
		count = 0
		while min_sum <= total_sum:
			min_sum += A[i]
			total_sum -= A[i]
			count += 1
			i += 1
		return count