Given two sorted arrays of distinct elements. There is only 1 difference between the arrays. First array has one element extra added in between. Find the index of the extra element.
Example 1:
Input:
N = 7
A[] = {2,4,6,8,9,10,12}
B[] = {2,4,6,8,10,12}
Output: 4
Explanation: In the second array, 9 is
missing and it's index in the first array
is 4.
Example 2:
Input:
N = 6
A[] = {3,5,7,9,11,13}
B[] = {3,5,7,11,13}
Output: 3
Your Task:
You don't have to take any input. Just complete the provided function findExtra() that takes array A[], B[] and size of A[] and return the valid index (0 based indexing).
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
2<=N<=10^{4}
1<=Ai<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: class Solution:

    def findExtra(self,a,b,n):

        #add code here

Solutions:
class Solution:

	def findExtra(self, array1, array2, n):
		n = n - 1
		(low, high) = (0, n - 1)
		finder = n
		while low <= high:
			mid = (low + high) // 2
			if array2[mid] == array1[mid]:
				low = mid + 1
			else:
				finder = mid
				high = mid - 1
		return finder


class Solution:

	def findExtra(self, a, b, n):
		for i in range(0, n - 1):
			if a[i] != b[i]:
				return i
		return n - 1


class Solution:

	def findExtra(self, a, b, n):
		(l, h) = (0, n - 2)
		if a[l] != b[l]:
			return 0
		if a[h] == b[h]:
			return n - 1
		while l <= h:
			mid = l + (h - l) // 2
			if a[mid] == b[mid]:
				l = mid + 1
			elif a[mid + 1] == b[mid] and a[mid] != b[mid - 1]:
				return mid
			else:
				h = mid - 1


class Solution:

	def findExtra(self, a, b, n):
		extraIndex = -1
		for i in range(0, len(b)):
			if a[i] != b[i]:
				extraIndex = i
				break
		if extraIndex == -1:
			extraIndex = len(b)
		return extraIndex


class Solution:

	def findExtra(self, a, b, n):
		suma = sum(a)
		sumb = sum(b)
		diff = suma - sumb
		return a.index(diff)


class Solution:

	def findExtra(self, a, b, n):
		return a.index(sum(a) - sum(b))


class Solution:

	def findExtra(self, a, b, n):
		ms = abs(sum(a) - sum(b))
		i = a.index(ms) if ms in a else b.index(ms)
		return i


class Solution:

	def findExtra(self, a, b, n):
		x = sum(a)
		y = sum(b)
		return a.index(x - y)


class Solution:

	def findExtra(self, a, b, n):
		c = a + b
		xor = 0
		for i in c:
			xor ^= i
		if xor in a:
			return a.index(xor)
		elif xor in b:
			return b.index(xor)


class Solution:

	def findExtra(self, a, b, n):
		element = set(a).difference(set(b)).pop()
		return a.index(element)


class Solution:

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


class Solution:

	def findExtra(self, a, b, n):
		target = sum(a) - sum(b)
		i = 0
		while i < len(a):
			if a[i] == target:
				return i
			i += 1


class Solution:

	def findExtra(self, a, b, n):
		d = set(a) - set(b)
		dif = list(d)
		return a.index(dif[0])


class Solution:

	def findExtra(self, a, b, n):
		s = sum(a) - sum(b)
		for i in range(n):
			if a[i] == s:
				return i


class Solution:

	def findExtra(self, a, b, n):
		i = 0
		try:
			while i <= n:
				if a[i] != b[i]:
					break
				i += 1
		except:
			pass
		return i


class Solution:

	def findExtra(self, a, b, n):
		d = sum(a)
		e = sum(b)
		c = d - e
		for i in range(len(a)):
			if a[i] == c:
				return i


class Solution:

	def findExtra(self, a, b, n):
		sum1 = sum(a)
		sum2 = sum(b)
		c = sum1 - sum2
		for i in range(0, len(a)):
			if a[i] == c:
				return i


class Solution:

	def findExtra(self, a, b, n):
		a_sum = sum(a)
		b_sum = sum(b)
		missing_element = a_sum - b_sum
		for index in range(len(a)):
			if a[index] == missing_element:
				return index


class Solution:

	def findExtra(self, a, b, n):
		extra = list(set(a).difference(set(b)))[0]
		return a.index(extra)


class Solution:

	def findExtra(self, a, b, n):
		target = list(set(a).difference(set(b)))[0]
		low = 0
		mid = (low + n - 1) // 2
		while a[mid] != target:
			if a[mid] > target:
				n = mid - 1
			elif a[mid] < target:
				low = mid + 1
			mid = (low + n) // 2
		return mid


class Solution:

	def findExtra(self, a, b, n):
		b.append('$')
		low = 0
		high = n
		while low < high:
			mid = low + (high - low) // 2
			if a[low] != b[low]:
				return low
			elif a[mid] != b[mid] and a[mid - 1] == b[mid - 1]:
				return mid
			elif a[mid] == b[mid]:
				low = mid
			elif a[mid] != b[mid]:
				high = mid


class Solution:

	def findExtra(self, arrayOne, arrayTwo, maxLength):
		biggerArray = arrayOne
		smallerArray = arrayTwo
		if len(arrayOne) < maxLength:
			biggerArray = arrayTwo
			smallerArray = arrayOne
		for i in range(0, maxLength):
			if i >= len(smallerArray) or biggerArray[i] != smallerArray[i]:
				return i


class Solution:

	def findExtra(self, a, b, n):
		if len(a) != len(b) + 1 and len(b) != len(a) + 1:
			return -1
		(low, high) = (0, n - 2)
		while low <= high:
			mid = (low + high) // 2
			if a[mid] == b[mid]:
				low = mid + 1
			else:
				high = mid - 1
		return low if low == n - 1 or a[low] != b[low] else low + 1


class Solution:

	def findExtra(self, a, b, n):
		suma = sum(a)
		sumb = sum(b)
		diff = abs(suma - sumb)
		start = 0
		end = n - 1
		while start <= end:
			mid = start + (end - start) // 2
			if a[mid] == diff:
				return mid
			elif a[mid] < diff:
				start = mid + 1
			else:
				end = mid - 1


class Solution:

	def findExtra(self, a, b, n):
		diff = n - 1
		for i in range(n - 1):
			if a[i] != b[i]:
				diff = i
				break
		return diff


class Solution:

	def findExtra(self, a, b, n):
		for i in range(len(b)):
			if a[i] != b[i]:
				return i
		return len(b)


class Solution:

	def findExtra(self, a, b, n):
		i = 0
		while i <= n - 1:
			if i == len(b):
				return i
			elif a[i] == b[i]:
				i += 1
			else:
				res = i
				return res
				break


class Solution:

	def findExtra(self, a, b, n):
		x = set(a)
		y = set(b)
		k = x - y
		for i in k:
			return a.index(i)


class Solution:

	def findExtra(self, a, b, n):
		m = len(b)
		for i in range(0, n // 2 + 1):
			if a[i] != b[i]:
				return i
			elif a[n - i - 1] != b[m - i - 1]:
				return n - i - 1
		return -1


class Solution:

	def findExtra(self, a, b, n):
		if len(a) > len(b):
			return a.index(sum(a) - sum(b))
		else:
			return a.index(sum(b) - sum(a))


class Solution:

	def findExtra(self, a, b, n):
		s1 = sum(a)
		s2 = sum(b)
		b = s1 - s2
		return a.index(b)


class Solution:

	def findExtra(self, a, b, n):
		diff = set(a) - set(b)
		ans = list(diff)
		return a.index(ans[0])


class Solution:

	def findExtra(self, a, b, n):
		a1 = sum(a)
		b1 = sum(b)
		k = a1 - b1
		return a.index(k)


class Solution:

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


class Solution:

	def findExtra(self, a, b, n):
		i = 0
		if a[-1] != b[-1]:
			return a.index(a[-1])
		while i <= n:
			if a[i] != b[i]:
				return a.index(a[i])
			i += 1


class Solution:

	def findExtra(self, arr1, arr2, n):
		n1 = len(arr1)
		n2 = len(arr2)
		if n1 == n2:
			return None
		if n1 < n2:
			(arr1, arr2) = (arr2, arr1)
			(n1, n2) = (n2, n1)
		(start, end) = (0, n1 - 1)
		while start <= end:
			mid = (start + end) // 2
			if mid >= n2 or arr1[mid] != arr2[mid]:
				end = mid - 1
			else:
				start = mid + 1
		return start


class Solution:

	def findExtra(self, a, b, n):
		sum1 = sum(a)
		sum2 = sum(b)
		res = sum1 - sum2
		ind = a.index(res)
		return ind


class Solution:

	def findExtra(self, a, b, n):
		set_dif = set(a).symmetric_difference(set(b))
		temp3 = list(set_dif)
		return a.index(temp3[0])


class Solution:

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


class Solution:

	def findExtra(self, a, b, n):
		Sum_a = sum(a)
		Sum_b = sum(b)
		ele = Sum_a - Sum_b
		return a.index(ele)


class Solution:

	def findExtra(self, a, b, n):
		i = 0
		j = n - 1
		while i <= j:
			if a[i] != b[i]:
				return i
			elif a[j] != b[j - 1]:
				return j
			i += 1
			j -= 1
		return -1


class Solution:

	def findExtra(self, a, b, n):
		x = set(a)
		y = set(b)
		lst = list(x - y)
		return a.index(lst[0])


class Solution:

	def findExtra(self, a, b, n):
		x = set(b)
		y = set(a)
		if len(a) > len(b):
			for i in range(len(a)):
				if a[i] not in x:
					return i
		else:
			for j in range(len(b)):
				if b[j] not in y:
					return j


class Solution:

	def findExtra(self, a, b, n):
		l = -1
		r = n - 1
		while l + 1 < r:
			m = (l + r) // 2
			if a[m] == b[m]:
				l = m
			else:
				r = m
		return l + 1


class Solution:

	def findExtra(self, a, b, n):
		index = 0
		start = 0
		end = n - 1
		while start <= end:
			mid = start + (end - start) // 2
			if mid < n - 1 and a[mid] == b[mid]:
				start = mid + 1
			else:
				index = mid
				end = mid - 1
		return index


class Solution:

	def findExtra(self, a, b, n):
		m = set(a) - set(b)
		q = list(m)
		return a.index(q[0])


class Solution:

	def findExtra(self, a, b, n):
		m = b
		m.append(0)
		for i in range(n):
			if a[i] != m[i]:
				return a.index(a[i])


class Solution:

	def findExtra(self, a, b, n):
		l = []
		l.extend(a)
		a = set(a)
		b = set(b)
		x = a.difference(b)
		a = list(a)
		x = list(x)
		return l.index(x[0])


class Solution:

	def findExtra(self, a, b, n):
		a1 = sum(a)
		b1 = sum(b)
		if a1 != b1:
			v = abs(a1 - b1)
		if v in a:
			return a.index(v)


class Solution:

	def findExtra(self, a, b, n):
		aa = set(a) - set(b)
		res = list(aa)
		return a.index(res[0])


class Solution:

	def findExtra(self, a, b, n):
		c = set(a)
		d = set(b)
		e = c - d
		return a.index(*e)