Find the missing element from an ordered array arr[], consisting of N elements representing an Arithmetic Progression(AP).
Note: There always exists an element which upon inserting into sequence forms Arithmetic progression. Boundary elements (first and last elements) are not missing.
Example 1:
Input:
N = 6
Arr[] = {2, 4, 8, 10, 12, 14}
Output: 6
Explanation: Actual AP should be 
2, 4, 6, 8, 10, 12, 14.
Example 2:
Input:
N = 6
Arr[] = {1, 6, 11, 16, 21, 31}
Output: 26
Explanation: Actual AP should be 
1, 6, 11, 16, 21, 26, 31.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMissing() which takes the array of integers arr[] and its size n as input parameters and returns an integer denoting the answer.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
2 <= N <= 10^{5}
0 <= |Arr[i]| <= 10^{7}
There will always be only one missing element.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def findMissing(self, arr, n):

        # code here

Solutions:
class Solution:

	def findMissing(self, arr, n):
		total = (n + 1) / 2 * (arr[0] + arr[n - 1])
		for i in arr:
			total -= i
		return int(total)


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		for i in range(n):
			if arr[i] + d != arr[i + 1]:
				return arr[i] + d


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		a = []
		a.append(arr[0])
		for i in range(1, len(arr) + 1):
			a.append(a[-1] + d)
		for i in range(n + 1):
			if arr[i] != a[i]:
				return a[i]


class Solution:

	def findMissing(self, arr, n):
		diff = (arr[n - 1] - arr[0]) // n
		for i in range(1, n):
			expected = arr[i - 1] + diff
			if arr[i] != expected:
				return expected
		return -1


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		i = 1
		while i < n:
			if arr[i] - arr[i - 1] == d:
				i += 1
				continue
			else:
				return arr[i - 1] + d
			i += 1


class Solution:

	def findMissing(self, arr, n):
		arr_sum = sum(arr)
		act_sum = (n + 1) * (arr[0] + arr[-1]) // 2
		return act_sum - arr_sum


class Solution:

	def findMissing(self, arr, n):
		value = abs(arr[0] - arr[1])
		value1 = abs(arr[-1] - arr[-2])
		value3 = min(value, value1)
		ans = 0
		if len(arr) > 2:
			for i in range(1, len(arr)):
				if arr[0] + i * value3 != arr[i]:
					ans = arr[0] + i * value3
					break
			return ans
		else:
			return int((arr[1] + arr[0]) / 2)


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		a = arr[n - 1] - arr[0]
		d = a // n
		for i in range(n - 1):
			if d == arr[i + 1] - arr[i]:
				continue
			else:
				missing = arr[i] + d
		return missing


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		(lo, hi) = (0, n - 1)
		while lo < hi:
			mid = (lo + hi) // 2
			if arr[mid + 1] - arr[mid] != d:
				return arr[mid] + d
			if arr[mid] - arr[mid - 1] != d:
				return arr[mid - 1] + d
			if arr[mid] == arr[0] + mid * d:
				lo = mid + 1
			else:
				hi = mid - 1


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		temp = arr[0]
		for i in range(2, len(arr) + 1, 1):
			ans = temp + (i - 1) * d
			if ans != arr[i - 1]:
				return ans


class Solution:

	def findMissing(self, arr, n):
		t = (n + 1) / 2 * (arr[0] + arr[-1])
		return int(t - sum(arr))


class Solution:

	def findMissing(self, arr, n):
		m = 0
		k = []
		if len(arr) == 2:
			return int((arr[0] + arr[1]) / 2)
		for i in range(n - 1):
			d = arr[i + 1] - arr[i]
			if len(k) == 0:
				k.append(d)
			if d > k[0]:
				return arr[i] + k[0]
			elif d < k[0]:
				return arr[i] - d


class Solution:

	def findMissing(self, arr, n):
		n = len(arr)
		expected_sum = (n + 1) * (arr[0] + arr[n - 1]) // 2
		actual_sum = sum(arr)
		return expected_sum - actual_sum


class Solution:

	def findMissing(self, arr, n):
		if n == 2:
			sum = (arr[0] + arr[1]) / 2
			return int(sum)
		dif = 0
		flag = 1
		num = 0
		for i in range(n - 1):
			if flag == 1:
				num = arr[i]
				dif = arr[i + 1] - arr[i]
			elif dif > arr[i + 1] - arr[i]:
				dif = arr[i + 1] - arr[i]
			elif dif < arr[i + 1] - arr[i]:
				num = arr[i]
			flag += 1
		return num + dif


class Solution:

	def findMissing(self, arr, n):
		sum = int((n + 1) / 2 * (arr[0] + arr[-1]))
		t = 0
		for i in arr:
			t += i
		t = sum - t
		return t


class Solution:

	def findMissing(self, a, n):
		sum1 = (n + 1) * (a[0] + a[n - 1]) // 2
		m = sum1 - sum(a)
		return m


class Solution:

	def findMissing(self, arr, n):
		ap_sum = (n + 1) * (arr[0] + arr[-1]) * 0.5
		return int(ap_sum - sum(arr))


class Solution:

	def findMissing(self, arr, n):
		f = arr[0]
		l = arr[-1]
		if (f + l) % 2:
			s = (n + 1) // 2
			s *= f + l
		else:
			s = (f + l) // 2
			s *= n + 1
		missing = s - sum(arr)
		return missing


class Solution:

	def findMissing(self, arr, n):
		diff = (arr[n - 1] - arr[0]) / n
		su1 = (n + 1) / 2 * (arr[0] + arr[n - 1])
		su2 = sum(arr)
		return int(su1) - su2


class Solution:

	def findMissing(self, arr, n):
		l = min(arr)
		m = max(arr)
		sums = (len(arr) + 1) / 2 * (l + m)
		return int(sums - float(sum(arr)))


class Solution:

	def findMissing(self, arr, n):
		l = 0
		r = len(arr) - 1
		d = (arr[n - 1] - arr[0]) // n
		while l <= r:
			mid = l + (r - l) // 2
			if (arr[mid] - arr[0]) // d == mid:
				l = mid + 1
			else:
				r = mid - 1
		return arr[r] + d


class Solution:

	def findMissing(self, a, n):
		s = 0
		for i in a:
			s += i
		return (n + 1) * (a[0] + a[n - 1]) // 2 - s


class Solution:

	def findMissing(self, arr, n):
		if len(arr) == 2:
			return (arr[0] + arr[1]) // 2
		x = arr[1] - arr[0] if arr[1] - arr[0] <= arr[-1] - arr[-2] else arr[-1] - arr[-2]
		num = arr[0]
		for i in arr:
			if i == num:
				num += x
			else:
				return num


class Solution:

	def findMissing(self, arr, n):
		d = (arr[-1] - arr[0]) / n
		for index in range(n):
			if arr[index] + d != arr[index + 1]:
				return int(arr[index] + d)


class Solution:

	def findMissing(self, arr, n):
		low = 0
		high = n - 1
		d = int((arr[n - 1] - arr[0]) / n)
		while low <= high:
			mid = int((low + high) / 2)
			if arr[mid + 1] - arr[mid] != d:
				return arr[mid] + d
			if arr[mid] - arr[mid - 1] != d:
				return arr[mid - 1] + d
			if mid > 0 and arr[mid] - arr[0] != mid * d:
				high = mid - 1
			else:
				low = mid + 1
		return -1


class Solution:

	def findMissing(self, arr, n):
		diff = int((arr[n - 1] - arr[0]) / n)
		s = 0
		e = n - 1
		while s <= e:
			mid = int((s + e) / 2)
			if arr[mid + 1] - arr[mid] != diff:
				return arr[mid] + diff
			if arr[mid] - arr[mid - 1] != diff:
				return arr[mid - 1] + diff
			if mid > 0 and arr[mid] - arr[0] != mid * diff:
				e = mid - 1
			else:
				s = mid + 1
		return -1


class Solution:

	def findMissing(self, arr, n):
		sum = (n + 1) / 2 * (arr[0] + arr[n - 1])
		i = 0
		j = n - 1
		while i < j:
			sum = sum - arr[i] - arr[j]
			i += 1
			j -= 1
		if i == j:
			sum = sum - arr[i]
		return int(sum)


class Solution:

	def findMissing(self, arr, n):
		x = (n + 1) * (arr[0] + arr[n - 1]) / 2
		y = sum(arr)
		return int(x - y)


class Solution:

	def findMissing(self, arr, n):
		l = arr[n - 1]
		a = arr[0]
		d = (l - a) / n
		for i in range(n):
			if arr[i + 1] - arr[i] != d:
				return int(arr[i] + d)


class Solution:

	def findMissing(self, arr, n):
		s = arr[0] + arr[n - 1]
		k = (n + 1) / 2
		t = k * s
		m = sum(arr)
		return int(t - m)


class Solution:

	def findMissing(self, arr, n):
		if n == 2:
			return int((arr[0] + arr[1]) / 2)
		diff = []
		for i in range(2):
			diff.append(arr[i + 1] - arr[i])
		diff.sort()
		rd = diff[0]
		for i in range(n):
			if arr[i + 1] - arr[i] != rd:
				return arr[i] + rd


class Solution:

	def findMissing(self, arr, n):

		def miss(arr, low, high, d):
			mid = round(low + (high - low) / 2)
			if arr[mid + 1] != arr[mid] + d:
				return arr[mid] + d
			elif arr[mid] > arr[0] + mid * d:
				return miss(arr, low, mid, d)
			else:
				return miss(arr, mid, high, d)
		d = int((arr[-1] - arr[0]) / n)
		return miss(arr, 0, n - 1, d)


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		sum = int((n + 1) * (2 * arr[0] + n * d) // 2)
		dup = 0
		for i in arr:
			dup += i
		return sum - dup


class Solution:

	def findMissing(self, arr, n):
		cd = int((arr[len(arr) - 1] - arr[0]) // len(arr))
		for i in range(len(arr) - 1):
			if arr[i] + cd != arr[i + 1]:
				return arr[i] + cd


class Solution:

	def findMissing(self, arr, n):
		res = 0
		if n == 2:
			res = (arr[0] + arr[1]) // 2
			return res
		if n > 2:
			dOne = arr[2] - arr[1]
			dTwo = arr[1] - arr[0]
			d = min(dOne, dTwo)
			for i in range(0, n - 1):
				if arr[i + 1] != arr[i] + d:
					res = arr[i] + d
			return res


class Solution:

	def findMissing(self, arr, n):
		a = arr[0]
		diff = (arr[-1] - a) // n
		for index in range(n):
			elem = a + index * diff
			if elem != arr[index]:
				return elem


class Solution:

	def findMissing(self, arr, n):
		arr.sort()
		if n == 2:
			return (arr[0] + arr[1]) // 2
		diff1 = arr[1] - arr[0]
		diff2 = arr[2] - arr[1]
		if diff1 == diff2:
			diff = diff1
		elif diff2 < diff1:
			return arr[0] + diff2
		else:
			return arr[1] + diff1
		for i in range(1, n):
			if arr[i] + diff != arr[i + 1]:
				return arr[i] + diff


import math

class Solution:

	def findMissing(self, arr, n):
		a = arr[0]
		l = arr[n - 1]
		s = (n + 1) * (a + l) // 2
		return s - sum(arr)


class Solution:

	def findMissing(self, arr, n):
		sum_arr = sum(arr)
		sum_act_arr = (n + 1) / 2 * (arr[0] + arr[n - 1])
		return int(sum_act_arr - sum_arr)


class Solution:

	def findMissing(self, arr, n):
		diff = (arr[n - 1] - arr[0]) // n
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if (arr[mid] - arr[0]) // diff == mid:
				low = mid + 1
			else:
				high = mid - 1
		return arr[high] + diff


class Solution:

	def findMissing(self, arr, n):
		if n == 2:
			return (arr[1] + arr[0]) // 2
		return check_missing(arr)

def check_missing(arr):
	d1 = arr[1] - arr[0]
	d2 = arr[2] - arr[1]
	if d1 >= 0:
		d = min(d1, d2)
	else:
		d = max(d1, d2)
	return binary_search(arr, 0, len(arr) - 1, d)

def binary_search(arr, l, r, d):
	supposed = (l + r) // 2
	if arr[supposed] == arr[l] + (supposed - l) * d:
		if arr[supposed + 1] - arr[supposed] == d:
			return binary_search(arr, supposed + 1, r, d)
		return arr[supposed] + d
	else:
		if arr[supposed] - arr[supposed - 1] == d:
			return binary_search(arr, l, supposed - 1, d)
		return arr[supposed] - d


class Solution:

	def findMissing(self, arr, n):
		a = arr[0]
		d = min(arr[1] - arr[0], arr[-1] - arr[-2])
		if n == 2:
			d = d // 2
		low = 0
		high = n - 1
		while low < high:
			mid = (low + high) // 2
			value = a + mid * d
			if arr[mid] > value:
				high = mid
			else:
				low = mid + 1
		else:
			return a + low * d


class Solution:

	def findMissing(self, arr, n):
		if len(arr) == 2:
			return (arr[0] + arr[1]) // 2
		nextTerm = arr[0]
		count = 0
		diff = min(arr[1] - arr[0], arr[2] - arr[1])
		while nextTerm < arr[-1]:
			if nextTerm != arr[count]:
				return nextTerm
			else:
				nextTerm += diff
				count = count + 1
		return nextTerm


class Solution:

	def findMissing(self, arr, n):
		d1 = arr[1] - arr[0]
		if n > 2:
			d2 = arr[2] - arr[1]
			d = min(d1, d2)
		else:
			d = d1
		if n == 2:
			return (arr[0] + arr[1]) // 2
		for i in range(n):
			if arr[i] != arr[0] + i * d:
				return arr[0] + i * d


class Solution:

	def findMissing(self, arr, n):
		if len(arr) == 2:
			return int(arr[1] - (arr[1] - arr[0]) / 2)
		else:
			diff = 10000
			for i in range(1, len(arr)):
				if arr[i] - arr[i - 1] < diff:
					diff = arr[i] - arr[i - 1]
			for i in range(1, len(arr)):
				if arr[i] - arr[i - 1] > diff:
					return arr[i] - diff


class Solution:

	def findMissing(self, arr, n):
		ap_sum = (n + 1) / 2 * (arr[0] + arr[n - 1])
		arr_sum = sum(arr)
		return int(ap_sum - arr_sum)


class Solution:

	def findMissing(self, a, n):
		d = (a[-1] - a[0]) // n
		k = 0
		for i in range(n):
			if a[i + 1] - a[i] != d:
				k = a[i] + d
				return k


class Solution:

	def findMissing(self, arr, n):
		first = arr[0]
		last = arr[-1]
		if (first + last) % 2:
			s = (n + 1) // 2
			s *= first + last
		else:
			s = (first + last) // 2
			s *= n + 1
		missing = s - sum(arr)
		return missing


class Solution:

	def findMissing(self, arr, n):
		sum = 0
		d = 0
		for i in arr:
			sum += i
		ap_sum = (n + 1) * (2 * arr[0] + n * (abs(arr[-1] - arr[0]) // n)) * 0.5
		missing_element = int(ap_sum - sum)
		return missing_element


class Solution:

	def findMissing(self, arr, n):
		lastEl = arr[-1]
		firstEl = arr[0]
		d = (lastEl - firstEl) // n
		for i in range(n - 1):
			currEl = arr[i]
			nextEl = arr[i + 1]
			if nextEl - currEl > d:
				return currEl + d


class Solution:

	def findMissing(self, arr, n):
		a = arr[0]
		d = (arr[n - 1] - arr[0]) // n
		l = 0
		h = n - 1
		while l <= h:
			m = (l + h) // 2
			an = a + m * d
			if arr[m + 1] - arr[m] == d:
				if an == arr[m]:
					l = m + 1
				else:
					h = m - 1
			else:
				return an + d


class Solution:

	def findMissing(self, arr, n):
		a = arr[n - 1] - arr[0]
		diff = a / len(arr)
		i = 0
		while i <= len(arr) - 1:
			if arr[i] + diff != arr[i + 1]:
				return int(arr[i] + diff)
				i = i + 1
			else:
				i = i + 1


class Solution:

	def findMissing(self, arr, n):
		(i, j) = (0, 1)
		d = (arr[n - 1] - arr[0]) // n
		while j < n:
			if arr[j] - arr[i] == d:
				i += 1
				j += 1
			else:
				return arr[i] + d
		return None


class Solution:

	def findMissing(self, arr, n):
		d = (arr[n - 1] - arr[0]) // n
		for (i, val) in enumerate(arr):
			if i > 0:
				if arr[i] - arr[i - 1] != d:
					return arr[i - 1] + d