Given two sequences, one is increasing sequence a[] and another a normal sequence b[], find the K-th missing element in the increasing sequence which is not present in the given sequence. If no K-th missing element is there output -1
 
Example 1:
Input : Arr[] = {0, 2, 4, 6, 8, 10, 12, 14, 15}
Brr[] = {4, 10, 6, 8, 12} and K = 3
Output : 14
Explanation:
The numbers from increasing sequence that
are not present in the given sequence are 0, 2, 14, 15.
The 3rd missing number is 14.
Example 2:
Input : Arr[] = {1, 2, 3, 4, 5}
Brr[] = {5, 4, 3, 1, 2} and K = 3
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 MissingNumber() that takes an array (a), another array (b), an element K, size of first array (n), size of the second array (m), and return the Kth missing number in an array a, if you can't find it return -1. The driver code takes care of the printing.
Expected Time Complexity: O(n + m).
Expected Auxiliary Space: O(m).
Constraints:
1 ≤ n,m,k ≤ 10^{5}
1 ≤ a[i] ≤ 10^{8}
1 ≤ b[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def MissingNumber(self, a, b, k, n1, n2): 

      

        # Complete the function

Solutions:
class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		d = {}
		for i in b:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		f = {}
		for i in a:
			if i in f:
				f[i] += 1
			else:
				f[i] = 1
		b = set(b)
		c = 0
		for i in a:
			if i not in b:
				c += 1
			if c == k:
				return i
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		s = set(b)
		for el in a:
			if el not in s:
				k = k - 1
				if k == 0:
					return el
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		s = set()
		for i in b:
			s.add(i)
		c = 0
		for i in a:
			if i not in s:
				c += 1
				if c == k:
					return i
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		for i in range(n1):
			if a[i] not in b:
				k -= 1
				if k == 0:
					return a[i]
		if k > 0:
			return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		l = []
		B = set(b)
		for i in a:
			if i not in B:
				l.append(i)
			if len(l) > k:
				break
		if len(l) >= k:
			return l[k - 1]
		else:
			return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		setti = set(b)
		for item in a:
			k -= item not in setti
			if k == 0:
				return item
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		m = {}
		for i in b:
			m[i] = True
		h = 1
		for i in a:
			if i not in m:
				if h == k:
					return i
				h += 1
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		dict2 = {}
		for j in range(n2):
			dict2[b[j]] = dict2.get(b[j], 0) + 1
		count = 0
		for element in range(n1):
			if a[element] not in dict2:
				count += 1
				if count == k:
					return a[element]
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		d = {}
		for x in b:
			d[x] = 1
		ls = []
		for x in a:
			if x not in d:
				ls.append(x)
		if len(ls) < k:
			return -1
		else:
			return ls[k - 1]


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		mydict = set()
		for i in b:
			mydict.add(i)
		count = 0
		for i in a:
			if i not in mydict:
				count += 1
			if count == k:
				return i
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		diff = set(a) - set(b)
		result = [o for o in a if o in diff]
		if len(result) >= k:
			return result[k - 1]
		else:
			return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		b = set(b)
		x = 0
		ls = []
		for i in range(len(a)):
			if a[i] not in b:
				x += 1
			if x == k:
				return a[i]
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		d = set()
		for i in range(n2):
			d.add(b[i])
		kth = 0
		for i in range(n1):
			if a[i] not in d:
				kth += 1
			if kth == k:
				return a[i]
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		ans = []
		gg = {}
		for i in b:
			if i not in gg:
				gg[i] = 1
		for i in a:
			if i not in gg:
				ans.append(i)
		try:
			return ans[k - 1]
		except:
			return -1


class Solution:

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

	def MissingNumber(self, a, b, k, n1, n2):
		b.sort()
		for i in range(n1):
			if self.BST(b, n2, a[i]) == -1:
				k -= 1
				if k == 0:
					return a[i]
		return -1


class Solution:

	def MissingNumber(self, a, b, k, n1, n2):
		dic = {i: True for i in b}
		i = 0
		while k > 0 and i < n1:
			try:
				x = dic[a[i]]
			except:
				k -= 1
				if k == 0:
					return a[i]
			i += 1
		return -1