Given an increasing sequence a[], we need to find the K-th missing contiguous element in the increasing sequence which is not present in the sequence. If no k-th missing element is there output -1.
Example 1:
Input : arr[ ] = {1, 3, 4, 5, 7} and K = 2
Output : 6
Explanation:
K = 2, We need to find the 2nd missing 
number in the array. Missing numbers are 
2 and 6. So 2nd missing number is 6.
 
Example 2:
Input : arr[ ] = {1, 2, 3, 4, 5, 6} and K = 1
Output :  -1 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function KthMissingElement() that takes an array (arr), sizeOfArray (n), an integer K and return the K^{th} missing number if present otherwise returns -1. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N, K, A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3





def KthMissingElement (arr,  n, K) : 

    #Complete the function



Solutions:
def KthMissingElement(arr, n, K):
	i = 0
	while i < n - 1:
		diff = arr[i + 1] - arr[i]
		if diff > K:
			return K + arr[i]
		else:
			K -= diff - 1
		i += 1
	return -1


def KthMissingElement(arr, n, K):
	num = arr[0]
	i = 0
	while i < n and K > 0:
		if arr[i] == num:
			i += 1
		else:
			K -= 1
		num += 1
	if K != 0:
		return -1
	return num - 1


def KthMissingElement(arr, n, K):
	i = arr[0]
	ind = 0
	missin = []
	n = len(arr)
	while ind < n and len(missin) < K:
		if i == arr[ind]:
			i += 1
			ind += 1
		else:
			missin.append(i)
			i += 1
	if len(missin) < K:
		return -1
	return missin[K - 1]


def KthMissingElement(arr, n, k):
	for i in range(n - 1):
		if arr[i + 1] > arr[i] + 1:
			temp = k
			k = k - (arr[i + 1] - arr[i] - 1)
		if k <= 0:
			return arr[i] + temp
	return -1


def KthMissingElement(arr, n, K):
	mi = min(arr)
	res = -1
	i = 0
	c = []
	while i < n - 1:
		if arr[i] + 1 == arr[i + 1]:
			i += 1
		else:
			arr[i] += 1
			c.append(arr[i])
	if len(c) < K:
		return res
	return c[K - 1]


def KthMissingElement(arr, n, K):
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] - (mid + arr[0]) < K:
			low = mid + 1
		else:
			high = mid - 1
	ans = arr[0] + K + low - 1
	if ans < arr[n - 1]:
		return ans
	return -1


def KthMissingElement(arr, n, K):
	ans = 0
	l = min(arr)
	r = max(arr)
	ind = 0
	for i in range(l, r):
		if i == arr[ind]:
			ind += 1
		else:
			K -= 1
			if K == 0:
				return i
	return -1


def KthMissingElement(arr, n, K):
	minn = min(arr)
	maxx = max(arr)
	j = 0
	for i in range(minn, maxx):
		if i != arr[j]:
			K -= 1
			if K == 0:
				return i
			continue
		j += 1
	return -1


def KthMissingElement(arr, n, K):
	hashset = set(arr)
	m = min(arr)
	n = max(arr)
	for i in range(m, n):
		if i not in hashset:
			K -= 1
		if K == 0:
			return i
	return -1


def KthMissingElement(arr, n, K):
	first = arr[0]
	res = []
	for index in range(n - 1):
		if arr[index + 1] != arr[index] + 1:
			res += list(range(arr[index] + 1, arr[index + 1]))
	return res[K - 1] if len(res) >= K else -1


def KthMissingElement(arr, n, K):
	temp = 0
	i = 0
	k = 0
	while i < n - 1:
		ans = arr[i + 1] - arr[i]
		if ans > K:
			return K + arr[i]
		else:
			K -= ans - 1
		i += 1
	return -1


def KthMissingElement(arr, n, K):
	for i in range(n - 1):
		if arr[i + 1] - arr[i] - 1 >= K:
			return arr[i] + K
		else:
			K -= arr[i + 1] - arr[i] - 1
	return -1


def KthMissingElement(arr, n, k):
	j = 0
	for i in range(arr[0], arr[-1]):
		if arr[j] == i:
			j += 1
		else:
			k -= 1
			if k == 0:
				return i
	return -1


def KthMissingElement(arr, n, K):
	min_ele = min(arr)
	ind = 0
	res = -1
	l = []
	c = 0
	while ind < n:
		if min_ele == arr[ind]:
			min_ele += 1
			ind += 1
		else:
			l.append(min_ele)
			min_ele += 1
			c += 1
		if c == K:
			return min_ele - 1
	return res


def KthMissingElement(arr, n, K):
	umap = {}
	mins = 99999
	maxs = -99999
	for i in range(n):
		umap[arr[i]] = 1
		if mins > arr[i]:
			mins = arr[i]
		if maxs < arr[i]:
			maxs = arr[i]
	counts = 0
	for i in range(mins, maxs + 1):
		if i not in umap:
			counts += 1
		if counts == K:
			return i
	return -1


def KthMissingElement(arr, n, K):
	cnt = 0
	num = arr[0]
	j = 0
	while j < n:
		if num == arr[j]:
			num += 1
			j += 1
		else:
			cnt += 1
			if cnt == K:
				return num
			num += 1
	return -1


def find_element(arr, val):
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == val:
			return True
		if arr[mid] > val:
			high = mid - 1
		else:
			low = mid + 1
	return False

def KthMissingElement(arr, n, k):
	for i in range(arr[0], arr[n - 1]):
		if not find_element(arr, i):
			k -= 1
		if k == 0:
			return i
	return -1


def KthMissingElement(arr, n, k):
	if n == arr[-1]:
		return -1
	if arr[-1] - n < k:
		return -1
	c = 0
	j = 0
	i = arr[0]
	while i < arr[0] + arr[-1]:
		if arr[j] == i:
			j += 1
			i += 1
		else:
			c += 1
			if c == k:
				return i
			i += 1


def KthMissingElement(arr, n, K):
	count = 0
	next = arr[0] + 1
	i = 1
	while i < n:
		if arr[i] != next:
			next += 1
			count += 1
		else:
			next = arr[i] + 1
			i += 1
		if count == K:
			return next - 1
	return -1


def KthMissingElement(arr, n, K):
	count = 0
	for i in range(0, len(arr) - 1):
		if arr[i + 1] - arr[i] > K - count:
			return arr[i] + (K - count)
		else:
			count += arr[i + 1] - arr[i] - 1
		if count == K:
			return arr[i] + 1
	return -1


def KthMissingElement(arr, n, K):
	a = list(range(min(arr), max(arr) + 1))
	a = set(a)
	b = a - set(arr)
	if len(b) < K:
		return -1
	b = list(b)
	b.sort()
	return b[K - 1]


def KthMissingElement(arr, n, K):
	lis = []
	i = 0
	while i < n - 1:
		if arr[i] + 1 == arr[i + 1]:
			i += 1
		else:
			arr[i] += 1
			lis.append(arr[i])
	if len(lis) < K:
		return -1
	return lis[K - 1]


def KthMissingElement(l, n, k):
	for i in range(0, n - 1):
		diff = l[i + 1] - l[i]
		if diff > k:
			return l[i] + k
		k -= diff - 1
	return -1


def KthMissingElement(arr, n, k):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] - (mid + arr[0]) < k:
			l = mid + 1
		else:
			r = mid - 1
	return l - 1 + arr[0] + k if l != n else -1


def KthMissingElement(arr, n, k):
	(lo, hi) = (0, n - 1)
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] - (mid + arr[0]) >= k:
			hi = mid - 1
		else:
			lo = mid + 1
	if lo == n:
		return -1
	return lo + k + arr[0] - 1


def KthMissingElement(arr, n, K):
	k = K
	a = arr[0] - 1
	n = 0
	for el in arr:
		c = el - a - 1
		n += c
		a = el
		if n >= k:
			break
	if n <= 0:
		return -1
	if n >= k:
		c = n - k
		a = a - c - 1
		return a
	return -1


def KthMissingElement(arr, n, K):
	count = 0
	for i in range(n - 1):
		diff = arr[i + 1] - arr[i]
		if diff > K:
			return arr[i] + K
		K -= diff - 1
	return -1


def KthMissingElement(arr, n, k):
	initial = arr[0]
	for i in range(n - 1):
		for j in range(initial, arr[i + 1]):
			if initial + 1 != arr[i + 1] and k == 1:
				return initial + 1
			elif initial + 1 != arr[i + 1]:
				k -= 1
			initial += 1
	return -1


def KthMissingElement(arr, n, K):
	ans = list()
	for i in range(1, n):
		if arr[i] - arr[i - 1] > 1:
			num = arr[i - 1] + 1
			while num < arr[i]:
				ans.append(num)
				num += 1
	if K > len(ans):
		return -1
	return ans[K - 1]


def KthMissingElement(arr, nn, K):
	l = []
	i = 0
	while i < nn - 1:
		if arr[i] + 1 == arr[i + 1]:
			i += 1
		else:
			arr[i] += 1
			l.append(arr[i])
	if len(l) < K:
		return -1
	return l[K - 1]


def KthMissingElement(arr, n, k):
	l = []
	i = 0
	while i < n - 1:
		if arr[i] + 1 == arr[i + 1]:
			i += 1
		else:
			arr[i] += 1
			l.append(arr[i])
	if len(l) < k:
		return -1
	else:
		return l[k - 1]


def KthMissingElement(arr, n, k):
	prev_miss = 0
	miss = 0
	for i in range(1, n):
		if arr[i] - arr[i - 1] > 1 and miss == 0:
			miss += arr[i] - arr[i - 1] - 1
		elif arr[i] - arr[i - 1] > 1:
			prev_miss = miss
			miss += arr[i] - arr[i - 1] - 1
		if miss > K:
			return arr[i - 1] + K - prev_miss
		elif miss == K:
			return arr[i] - 1
	return -1


def KthMissingElement(arr, n, K):
	c = 0
	a = arr[-1]
	b = 0
	for i in range(arr[0], a + 1):
		if i == arr[b]:
			b += 1
		else:
			c += 1
			if c == K:
				return i
	return -1


def KthMissingElement(arr, n, K):
	diff = 0
	ans = 0
	cont = K
	flag = 0
	for i in range(n - 1):
		diff = 0
		if arr[i] + 1 != arr[i + 1]:
			diff += arr[i + 1] - arr[i] - 1
			if diff >= cont:
				ans = arr[i] + cont
				flag = 1
				break
			else:
				cont -= diff
	if flag:
		return ans
	else:
		return -1


def KthMissingElement(arr, n, k):
	cou = 0
	x = arr[-1]
	t = 0
	for i in range(arr[0], x + 1):
		if i == arr[t]:
			t += 1
		else:
			cou += 1
		if cou == k:
			return i
	return -1


def KthMissingElement(arr, n, k):
	l = 0
	h = n - 1
	mid = 0
	while l <= h:
		mid = l + h >> 1
		n_l = arr[mid] - (mid + arr[0])
		if n_l < k:
			l = mid + 1
		else:
			h = mid - 1
	if l == n:
		return -1
	else:
		return l - 1 + arr[0] + k


import numpy as np

def KthMissingElement(arr, n, K):
	a = np.arange(arr[0], arr[n - 1] + 1)
	b = list(set(a) ^ set(arr))
	if len(b) > K:
		return b[K - 1]
	else:
		return -1


def missingAtIndex(start, end, index):
	return end - (start + index)

def KthMissingElement(arr, N, K):
	if N <= 1:
		return -1
	(low, high) = (0, N - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] - (arr[0] + mid) < K:
			low = mid + 1
		else:
			high = mid - 1
	if low == N:
		return -1
	return low - 1 + arr[0] + K


def KthMissingElement(arr, n, K):
	count = 0
	for index in range(0, n - 1):
		if arr[index] + 1 != arr[index + 1]:
			diff = arr[index + 1] - arr[index]
			if diff > K:
				return arr[index] + K
			else:
				K -= diff - 1
	return -1


def KthMissingElement(arr, n, K):
	prev_missing = 0
	missing = 0
	for i in range(1, n):
		if arr[i] - arr[i - 1] > 1 and missing == 0:
			missing += arr[i] - arr[i - 1] - 1
		elif arr[i] - arr[i - 1] > 1:
			prev_missing = missing
			missing += arr[i] - arr[i - 1] - 1
		if missing > K:
			return arr[i - 1] + K - prev_missing
		elif missing == K:
			return arr[i] - 1
	return -1


def KthMissingElement(arr, n, K):
	l = 0
	h = n - 1
	while l <= h:
		mid = (l + h) // 2
		if arr[mid] - (mid + arr[0]) >= K:
			h = mid - 1
		else:
			l = mid + 1
	if l == n:
		return -1
	return l + K + arr[0] - 1


def countMissing(actual, expected):
	return actual - expected

def KthMissingElement(arr, n, K):
	ind = 0
	cnt = 0
	for i in range(arr[0], arr[-1] + 1):
		if arr[ind] == i:
			if ind != n - 1:
				ind += 1
		else:
			cnt += 1
			if cnt == K:
				return i
	return -1


def KthMissingElement(arr, n, K):
	cnt = 0
	curr = arr[0]
	i = 0
	while i < n:
		if arr[i] != curr:
			cnt += 1
		else:
			i += 1
		if cnt == K:
			return curr
		curr += 1
	return -1


def KthMissingElement(arr, n, K):
	k_cnt = 0
	for i in range(len(arr) - 1):
		df = arr[i + 1] - arr[i]
		cnt = df - 1
		if k_cnt + cnt >= K:
			return arr[i] + K - k_cnt
		else:
			k_cnt += cnt
	return -1


def missing(n, a):
	return a[n] - a[0] - n

def KthMissingElement(a, n, k):
	low = 0
	high = n - 1
	while low <= high:
		mid = low + (high - low) // 2
		nums_missing = missing(mid, a)
		if nums_missing >= k:
			high = mid - 1
		else:
			low = mid + 1
	if low == n:
		return -1
	return a[low - 1] - missing(low - 1, a) + k


def KthMissingElement(a, n, K):
	low = 0
	high = n - 1
	while low <= high:
		mid = low + (high - low) // 2
		if a[mid] - a[0] - mid < K:
			low = mid + 1
		else:
			high = mid - 1
	if low == n:
		return -1
	return a[0] + high + K


def KthMissingElement(arr, n, k):
	for i in range(n - 1):
		diff = arr[i + 1] - arr[i]
		if diff > k:
			return arr[i] + k
		k -= diff - 1
	return -1


def KthMissingElement(arr, n, K):
	ans = []
	c = min(arr)
	b = max(arr)
	d = 0
	for i in range(n - 1):
		diff = arr[i + 1] - arr[i]
		if diff > K:
			return arr[i] + K
		K -= diff - 1
	else:
		return -1


def KthMissingElement(arr, n, K):
	s = arr[0]
	e = arr[-1]
	k = 0
	m = 0
	for i in range(s, e + 1):
		if m < K and i <= e:
			if i == arr[k]:
				k += 1
			else:
				m += 1
		elif m == K:
			return i - 1
	return -1


def KthMissingElement(arr, n, K):
	(lo, hi) = (0, n - 1)
	missingNumbers = 0
	startNumber = arr[0]
	mid = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		correctIndex = arr[mid] - startNumber
		missingNumbers = correctIndex - mid
		if missingNumbers >= K:
			hi = mid - 1
		else:
			lo = mid + 1
	if lo == n:
		return -1
	if missingNumbers < K:
		return arr[mid] + (K - missingNumbers)
	return arr[mid] + (K - missingNumbers) - 1


def KthMissingElement(arr, n, K):
	x = max(arr)
	y = min(arr)
	res = []
	a = []
	for i in range(y, x + 1):
		res.append(i)
	d1 = dict()
	for i in arr:
		if i in d1:
			d1[i] = d1[i] + 1
		else:
			d1[i] = 1
	d2 = dict()
	for i in res:
		if i in d2:
			d2[i] = d2[i] + 1
		else:
			d2[i] = 1
	for (p, v) in d2.items():
		if p not in d1:
			a.append(p)
	if len(a) < K:
		return -1
	else:
		a.sort()
		return a[K - 1]


def KthMissingElement(arr, n, k):
	cnt = 0
	curr = arr[0]
	missing = None
	i = 0
	while i < len(arr):
		if arr[i] == curr:
			i += 1
			curr += 1
		else:
			missing = curr
			cnt += 1
			curr += 1
		if cnt == k:
			return missing
	return -1


def KthMissingElement(arr, n, K):
	d = {}
	for i in arr:
		d[i] = 1
	ans = []
	for i in range(min(arr), max(arr)):
		if i not in d:
			ans.append(i)
	if len(ans) < K:
		return -1
	return ans[K - 1]


def KthMissingElement(arr, n, K):
	f = min(arr)
	g = max(arr)
	l = []
	if g - f + 1 == len(arr):
		return -1
	for i in range(n - 1):
		if arr[i + 1] - arr[i] > 1:
			d = arr[i + 1] - arr[i]
			for j in range(1, d):
				l.append(arr[i] + j)
				if len(l) == K:
					return l[-1]
	return -1


def KthMissingElement(arr, n, K):
	Set = set(arr)
	for i in range(arr[0], arr[-1] + 1):
		if i not in Set:
			K -= 1
		if K == 0:
			return i
	return -1


def KthMissingElement(arr, n, k):
	a = arr[0]
	i = 0
	while i < n:
		if arr[i] == a:
			a += 1
			i += 1
		else:
			k -= 1
			if not k:
				return a
			a += 1
	return -1


def KthMissingElement(arr, n, K):
	missing_count = 0
	for i in range(n - 1):
		if arr[i] + 1 != arr[i + 1]:
			c = K - missing_count
			d = arr[i + 1] - arr[i] - 1
			missing_count = missing_count + d
			if missing_count >= K:
				return arr[i] + c
	else:
		return -1


def KthMissingElement(arr, n, K):
	s = set()
	N = arr[n - 1]
	t = arr[0]
	count = 0
	for i in range(0, n):
		s.add(arr[i])
	for i in range(t, N):
		if i not in s:
			count += 1
			if count == K:
				return i
	return -1


def KthMissingElement(a, n, k):
	(val, cnt) = (0, 0)
	lp = a[0]
	maxx = a[n - 1]
	i = 0
	for it in range(a[0], maxx):
		if lp == a[i]:
			i = i + 1
			lp += 1
		else:
			val = lp
			cnt += 1
			lp += 1
		if cnt == k:
			return val
	return -1
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	res = KthMissingElement(arr, n, K)
	print(res)


def KthMissingElement(arr, n, k):
	a = []
	for i in range(0, n - 1):
		x = arr[i]
		while x + 1 != arr[i + 1]:
			k -= 1
			x += 1
			if k == 0:
				return x
		if k == 0:
			return a[i] + 1
	return -1


def KthMissingElement(a, n, k):
	(i, j) = (0, a[0])
	skip = 0
	while i < n:
		if a[i] != j:
			skip += 1
			if k == skip:
				return j
			j += 1
		else:
			i += 1
			j += 1
	return -1


def KthMissingElement(arr, n, K):
	f = arr[0]
	c = 0
	l = 1
	while l < n:
		if arr[l] != f + l:
			c += 1
			f += 1
			if c == K:
				return f + l - 1
		else:
			l += 1
	return -1


def KthMissingElement(arr, n, K):
	currentIndex = 0
	expectedNextItem = arr[currentIndex] + 1
	numberOfMissingItems = 0
	while numberOfMissingItems < K and currentIndex < n - 1:
		if arr[currentIndex + 1] > expectedNextItem:
			numberOfMissingItems += 1
			expectedNextItem += 1
		else:
			currentIndex += 1
			expectedNextItem = arr[currentIndex] + 1
	if numberOfMissingItems == K:
		return expectedNextItem - 1
	return -1


def KthMissingElement(arr, n, K):
	maxn = max(arr)
	s = min(arr)
	tag = [0] * (maxn + 1)
	missing = []
	for i in range(0, n):
		tag[arr[i]] = 1
	for i in range(s, maxn + 1):
		if tag[i] == 0:
			missing.append(i)
	if len(missing) < K:
		return -1
	else:
		res = missing[K - 1]
		return res