Given an array of integers a of length n and a value k. You have to find out the maximum possible numbers within 10^{9}whose sum does not exceed k  but are not present in the array.
Example 1:
Input: n = 4, 
       k = 14,
       a = {4, 6, 12, 8}
Output: 4
Explaination: The integers 1, 2, 3 and 5.
Example 2:
Input: n = 4,
       k = 25, 
       a = {5, 6, 7, 8}
Output: 5
Explaination: The integers are 1, 2, 3, 4 and 9.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxNumbers() which takes n, k, and array as input parameters and returns the maximum number of integers that can be selected.
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ a[i], k ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def maxNumbers(self, n, k, a):

        # code here

Solutions:
class Solution:

	def maxNumbers(self, n, k, arr):
		e = 1
		s = set(arr)
		r = 0
		while True:
			if not e in s:
				if k >= e:
					k -= e
					r += 1
				else:
					break
			e += 1
		return r


class Solution:

	def maxNumbers(self, n, k, a):
		a.sort()
		j = kk = s = 0
		for i in range(1, 10 ** 9 + 1):
			if j < len(a) and i == a[j]:
				j += 1
			else:
				kk += 1
				s += i
			if s > k:
				return kk - 1


class Solution:

	def maxNumbers(self, n, k, a):
		sm = 0
		cnt = 0
		i = 0
		while sm < k:
			i += 1
			if i not in a:
				cnt += 1
				sm += i
		return cnt - 1


class Solution:

	def maxNumbers(self, n, k, a):
		sum = 0
		l1 = []
		for i in range(1, k):
			if i not in a:
				sum = sum + i
				if sum <= k:
					l1.append(i)
				else:
					break
		return len(l1)


class Solution:

	def maxNumbers(self, n, k, a):
		s = set(a)
		c = 0
		for i in range(1, 1000000000):
			if i not in s:
				if k - i >= 0:
					c += 1
					k -= i
				else:
					break
		return c


class Solution:

	def maxNumbers(self, n, k, a):
		l = []
		s = 0
		for i in range(1, k + 1):
			if i not in a and s + i < k:
				s = i + s
				l.append(i)
			if s + i > k:
				break
		return len(l)


class Solution:

	def maxNumbers(self, n, k, a):
		count = 0
		sum = 0
		for i in range(1, k):
			sum = sum + i
			if i not in a:
				if sum < k:
					count = count + 1
				elif sum > k:
					break
			else:
				sum = sum - i
		return count


class Solution:

	def maxNumbers(self, n, k, a):
		a.sort()
		count = 0
		index = 0
		sum = 0
		for i in range(1, k):
			if index < n:
				if i < a[index] and sum < k:
					count += 1
					sum += i
					if sum > k:
						count -= 1
						return count % 10 ** 9
				elif i == a[index]:
					index += 1
				else:
					index += 1
			else:
				sum += i
				count += 1
				if sum > k:
					count -= 1
					return count % 10 ** 9
		return 0


class Solution:

	def maxNumbers(self, n, k, a):
		sum = 0
		num = 0
		for i in range(1, 10 ** 9):
			if i not in a:
				sum += i
				if sum <= k:
					num += 1
				elif sum > k:
					return num


class Solution:

	def maxNumbers(self, n, k, a):
		i = 1
		s = 0
		c = 0
		while s < k and i <= 1000000000:
			if i not in a:
				s += i
				c += 1
			i += 1
		return c - 1


class Solution:

	def maxNumbers(self, n, k, a):
		summa = 0
		count = 0
		a = sorted(set(a))
		n = len(a)
		i = 1
		j = 0
		while True:
			if j < n:
				if i == a[j]:
					i += 1
					j += 1
					continue
			summa += i
			i += 1
			if summa > k:
				return count
			count += 1


class Solution:

	def maxNumbers(self, n, k, a):
		a = sorted(a)
		total = k
		count = 0
		i = 1
		j = 0
		while total > 0:
			if i != a[j]:
				total -= i
				if total >= 0:
					count += 1
				else:
					break
			elif j < n - 1:
				j += 1
			i += 1
		return count


class Solution:

	def maxNumbers(self, n, k, a):
		sum = 0
		i = 0
		count = 0
		while sum < k:
			i = i + 1
			sum = sum + i
			count = count + 1
			if i in a:
				sum = sum - i
				count = count - 1
		if sum > k:
			return count - 1
		else:
			return count


class Solution:

	def maxNumbers(self, n, k, a):
		ct = 0
		s = 0
		for i in range(1, 10 ** 9):
			if i not in a:
				s += i
				if s < k:
					ct += 1
				else:
					break
		return ct


class Solution:

	def maxNumbers(self, n, k, a):
		su = 0
		counter = 1
		ans = 0
		while su < k:
			if counter not in a:
				su += counter
				ans += 1
			counter += 1
		return ans - 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, k) = [int(x) for x in input().split()]
		a = input().split()
		for it in range(n):
			a[it] = int(a[it])
		ob = Solution()
		print(ob.maxNumbers(n, k, a))


class Solution:

	def maxNumbers(self, n, k, a):
		hashh = set()
		for i in a:
			hashh.add(i)
		s = 0
		i = 1
		li = []
		while s <= k:
			if i not in hashh:
				if s + i <= k:
					s += i
					li.append(i)
				else:
					return len(li)
			i += 1
		return len(li)


class Solution:

	def maxNumbers(self, n, k, a):
		sett = set(a)
		res = 0
		summ = 0
		for i in range(1, 10 ** 9 + 1):
			if i not in sett:
				summ += i
				if summ < k:
					res += 1
				else:
					break
		return res


class Solution:

	def maxNumbers(self, n, k, a):
		cnt = 1
		res = 0
		a.sort()
		sum = 0
		for i in range(0, n):
			while cnt < a[i] and sum + cnt < k:
				sum = sum + cnt
				cnt = cnt + 1
				res = res + 1
			cnt = cnt + 1
		while sum + cnt < k:
			sum = sum + cnt
			res = res + 1
			cnt = cnt + 1
		return res


class Solution:

	def maxNumbers(self, n, k, a):
		hset = set(a)
		cnts = 0
		i = 1
		tot = 0
		while True:
			if tot + i > k:
				break
			if i not in hset:
				tot += i
				cnts += 1
			i += 1
		return cnts


class Solution:

	def maxNumbers(self, n, k, a):
		sum1 = 0
		count = 0
		for i in range(1, k + 1):
			if i not in a:
				sum1 = sum1 + i
				count = count + 1
				if sum1 > k:
					break
		return count - 1


class Solution:

	def maxNumbers(self, n, k, a):
		a.sort()
		val = 0
		count = 0
		i = 0
		temp = 1
		while val < k:
			if i < n and temp == a[i]:
				i += 1
				temp += 1
				continue
			val += temp
			count += 1
			temp += 1
		return count - 1


class Solution:

	def maxNumbers(self, n, k, a):
		from collections import Counter
		c = Counter(a)
		cs = 0
		temp = 1
		res = 0
		while k > 0:
			if temp not in c:
				if k - temp > 0:
					res += 1
				k -= temp
			temp += 1
		return res


class Solution:

	def maxNumbers(self, n, k, a):
		sum_ = 0
		c = 0
		for i in range(1, 1000000000):
			if i not in a:
				sum_ += i
				c += 1
			if sum_ > k:
				c -= 1
				break
		return c


class Solution:

	def maxNumbers(self, n, k, a):
		array = a
		total = 0
		num_count = 0
		for num in range(1, k + 1):
			if num not in array:
				if total + num < k:
					total += num
					num_count += 1
				else:
					break
		return num_count


class Solution:

	def maxNumbers(self, n, k, a):
		a.sort()
		sm = 0
		count = 0
		for i in range(k):
			if sm + i > k:
				break
			if i in a:
				continue
			sm += i
			count += 1
		return count - 1


class Solution:

	def maxNumbers(self, n, k, a):
		su = 0
		c = 0
		a.sort()
		for i in range(1, k):
			if su + i > k:
				break
			elif i not in a:
				su += i
				c += 1
		return c


class Solution:

	def maxNumbers(self, n, k, a):
		arr = sorted(a)
		d = 1
		i = 0
		summ = 0
		count = 0
		while summ < k:
			if i < n and d == arr[i]:
				d += 1
				i += 1
			else:
				summ += d
				if summ >= k:
					break
				else:
					d += 1
					count += 1
		return count


class Solution:

	def maxNumbers(self, n, k, a):
		sum = 0
		i = 1
		a = set(a)
		ans = 0
		while sum + i <= k:
			if i not in a:
				sum += i
				ans += 1
			i += 1
		return ans


class Solution:

	def maxNumbers(self, n, k, a):
		count = 0
		sum_of_numbers = 0
		for i in range(1, k):
			if a.count(i) == 0:
				sum_of_numbers = sum_of_numbers + i
				if sum_of_numbers > k:
					return count
				else:
					count = count + 1
		return count


class Solution:

	def maxNumbers(self, n, k, a):
		hash = {}
		for i in range(n):
			hash[a[i]] = 1
		count = 0
		i = 1
		while i < k:
			if i not in hash:
				k -= i
				count += 1
			i += 1
		return count


class Solution:

	def maxNumbers(self, n, k, a):
		ans = 0
		a.sort()
		i = 1
		while i < k:
			if i not in a:
				k = k - i
				ans += 1
			else:
				pass
			if k == 0 or k < 0:
				break
			i += 1
		return ans


class Solution:

	def maxNumbers(self, n, k, a):
		i = 1
		sumi = 0
		track = 0
		while sumi <= k:
			if i in a:
				i += 1
				continue
			else:
				sumi += i
				track += 1
				i += 1
		return track - 1


class Solution:

	def maxNumbers(self, n, k, a):
		sum = 0
		count = 0
		for i in range(1, 10 ** 9):
			if i in a:
				continue
			if sum + i > k:
				return count
			else:
				sum += i
				count += 1


class Solution:

	def maxNumbers(self, n, k, a):
		summ = 0
		cnt = 0
		for i in range(1, 1000000000):
			if i not in a:
				if summ + i <= k:
					summ += i
					cnt += 1
				else:
					break
		return cnt