Given an array A of size N. The contents of A are copied into another array B and numbers are shuffled. Also, one element is removed from B. The task is to find the missing element.
 
Example 1:
Input : 
A[] = {4, 8, 1, 3, 7}
B[] = {7, 4, 3, 1}
Output : 8
Explanation:
8 is the only element missing from B.
 
Example 2:
Input : 
A[] = {12, 10, 15, 23, 11, 30}
B[] = {15, 12, 23, 11, 30}
Output : 10
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMissing() which takes the array A[], B[] and its size N and N-1, respectively as inputs and returns the missing number.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
2 <= N <= 10^{6}
1 <= A, B <= 10^{18}
Array may also contain duplicates.

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3


class Solution:
    def findMissing(self,  a, b, n):
        # code here
    


Solutions:
class Solution:

	def findMissing(self, a, b, n):
		return sum(a) - sum(b)


class Solution:

	def findMissing(self, a, b, n):
		s1 = s2 = 0
		for i in range(len(a)):
			s1 += a[i]
		for j in range(len(b)):
			s2 += b[j]
		return abs(s1 - s2)


class Solution:

	def findMissing(self, a, b, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in b:
			d[i] -= 1
		for i in d:
			if d[i] != 0:
				return i


class Solution:

	def findMissing(self, a, b, n):
		xor = 0
		for i in a:
			xor ^= i
		for i in b:
			xor ^= i
		return xor


class Solution:

	def findMissing(self, a, b, n):
		ans = 0
		for i in range(n):
			ans = a[i] ^ ans
		for j in range(n - 1):
			ans = b[j] ^ ans
		return ans


class Solution:

	def findMissing(self, a, b, n):
		dict = {}
		a.extend(b)
		for i in a:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		for key in dict:
			if dict[key] == 1 or dict[key] % 2 != 0:
				return key


class Solution:

	def findMissing(self, a, b, n):
		one = 0
		two = 0
		for i in a:
			one = one ^ i
		for j in b:
			two = two ^ j
		return one ^ two


class Solution:

	def findMissing(self, a, b, n):
		c = abs(sum(a) - sum(b))
		return c


class Solution:

	def findMissing(self, a, b, n):
		s1 = sum(a)
		s2 = sum(b)
		return s1 - s2


class Solution:

	def findMissing(self, a, b, n):
		anum = 0
		for i in range(n):
			anum = anum ^ a[i]
		for i in range(n - 1):
			anum = anum ^ b[i]
		return anum


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		for i in range(n - 1):
			if a[i] != b[i]:
				return a[i]
		else:
			return a[-1]


class Solution:

	def findMissing(self, a, b, n):
		sa = sum(a)
		sb = sum(b)
		return sa - sb


class Solution:

	def findMissing(self, a, b, n):
		sum_a = sum(a)
		sum_b = sum(b)
		return sum_a - sum_b


from collections import Counter

class Solution:

	def findMissing(self, a, b, n):
		d = Counter(a)
		count = 0
		for i in b:
			d[i] -= 1
		for (key, value) in d.items():
			if value != 0:
				return key


class Solution:

	def findMissing(self, a, b, n):
		value = 0
		for item in a:
			value = value ^ item
		for item in b:
			value = value ^ item
		return value


class Solution:

	def findMissing(self, a, b, n):
		x = sum(a)
		y = sum(b)
		return x - y


class Solution:

	def findMissing(self, a, b, n):
		aSum = 0
		bSum = 0
		for elem in a:
			aSum += elem
		for elem in b:
			bSum += elem
		return aSum - bSum


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		for i in range(len(b)):
			if a[i] != b[i]:
				return a[i]
				break
		if i == len(b) - 1:
			return max(a)


class Solution:

	def findMissing(self, a, b, n):
		l = sum(a)
		ll = sum(b)
		return l - ll


class Solution:

	def findMissing(self, a, b, n):
		s = 0
		for i in range(0, len(a)):
			s = s ^ a[i]
		v = s
		for j in range(0, len(b)):
			v = v ^ b[j]
		return v


class Solution:

	def findMissing(self, a, b, n):
		for i in b:
			a.append(i)
		ans = 0
		a.sort()
		for i in range(0, len(a)):
			ans ^= a[i]
		return ans


class Solution:

	def findMissing(self, a, b, n):
		ad = {}
		bd = {}
		for j in a:
			if j in ad:
				ad[j] += 1
			else:
				ad[j] = 1
		for j in b:
			if j in bd:
				bd[j] += 1
			else:
				bd[j] = 1
		e = -1
		for j in ad:
			if ad.get(j) != bd.get(j):
				e = j
		return e


class Solution:

	def findMissing(self, a, b, n):
		for i in b:
			a.append(i)
		ans = 0
		for i in a:
			ans = ans ^ i
		return ans


class Solution:

	def findMissing(self, a, b, n):
		xoR = 0
		i = 0
		j = 0
		while i < n:
			xoR ^= a[i]
			i += 1
		while j < n - 1:
			xoR ^= b[j]
			j += 1
		return xoR


class Solution:

	def findMissing(self, a, b, n):
		sum_a = 0
		sum_b = 0
		for i in range(n):
			sum_a += a[i]
		for i in range(n - 1):
			sum_b += b[i]
		return abs(sum_b - sum_a)


class Solution:

	def findMissing(self, a, b, n):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = {}
		for i in b:
			if i not in d1:
				d1[i] = 1
			else:
				d1[i] += 1
		for i in a:
			if d1.get(i) == None or d[i] != d1[i]:
				return i


class Solution:

	def findMissing(self, a, b, n):
		A = sum(a)
		B = sum(b)
		return A - B


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		i = 0
		j = 0
		while j < n - 1:
			if a[i] == b[i]:
				i += 1
				j += 1
			else:
				break
		return a[i]


class Solution:

	def findMissing(self, a, b, n):
		a_sm = sum(a)
		b_sm = sum(b)
		return a_sm - b_sm


class Solution:

	def findMissing(self, a: list, b: list, n=None) -> int:
		n = n if n is not None else len(a)
		(sum_a, sum_b) = (a[n - 1], 0)
		for i in range(n - 1):
			(sum_a, sum_b) = (sum_a + a[i], sum_b + b[i])
		return sum_a - sum_b


class Solution:

	def findMissing(self, a, b, n):
		sumA = 0
		sumB = 0
		for i in range(0, n):
			sumA = sumA + a[i]
		for i in range(0, n - 1):
			sumB = sumB + b[i]
		return sumA - sumB


class Solution:

	def findMissing(self, a, b, n):
		dict1 = {}
		dict2 = {}
		for i in range(len(a)):
			dict1[a[i]] = dict1.get(a[i], 0) + 1
		for j in range(len(b)):
			dict2[b[j]] = dict2.get(b[j], 0) + 1
		for key in dict1:
			if key not in dict2 or dict1[key] > dict2[key]:
				return key


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		res = []
		if a == b:
			return 0
		else:
			return sum(a) - sum(b)


class Solution:

	def findMissing(self, a, b, n):
		num = a[n - 1]
		for i in range(n - 1):
			num ^= a[i] ^ b[i]
		return num


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		for i in range(n):
			try:
				if a[i] != b[i]:
					return a[i]
			except:
				return a[n - 1]


class Solution:

	def findMissing(self, a, b, n):
		ans = 0
		for ele in a:
			ans ^= ele
		for ele in b:
			ans ^= ele
		return ans


class Solution:

	def findMissing(self, a, b, n):
		d = {}
		for ele in a:
			if ele in d:
				d[ele] += 1
			else:
				d[ele] = 1
		d1 = {}
		for ele in b:
			if ele in d1:
				d1[ele] += 1
			else:
				d1[ele] = 1
		for ele in d:
			if not ele in d1:
				return ele
			elif not d[ele] == d1[ele]:
				return ele


from collections import Counter

class Solution:

	def findMissing(self, a, b, n):
		d1 = Counter(b)
		for num in a:
			if num not in d1:
				return num
			elif d1[num] == 1:
				del d1[num]
			else:
				d1[num] -= 1


class Solution:

	def findMissing(self, a, b, n):
		num1 = sum(a)
		num2 = sum(b)
		return num1 - num2


class Solution:

	def findMissing(self, a, b, n):
		a1 = sum(a)
		b1 = sum(b)
		return a1 - b1


class Solution:

	def findMissing(self, a, b, n):
		a.sort()
		b.sort()
		ai = n - 1
		bi = n - 2
		while ai >= 0:
			if a[ai] != b[bi]:
				return a[ai]
			ai -= 1
			bi -= 1
		return a[0]


class Solution:

	def findMissing(self, a, b, n):
		frq = dict()
		for i in range(0, len(a)):
			if a[i] in frq:
				frq[a[i]] = frq[a[i]] + 1
			else:
				frq[a[i]] = 1
		for i in range(0, len(b)):
			if b[i] in frq:
				frq[b[i]] = frq[b[i]] + 1
			else:
				frq[b[i]] = 1
		if len(frq) == 1:
			return a[0]
		for (key, val) in frq.items():
			if val % 2 != 0:
				return key
		return a[n - 1]