Given a sorted array A[] of N positive integers having all the numbers occurring exactly twice, except for one number which will occur only once. Find the number occurring only once.
Example 1:
Input:
N = 5
A = {1, 1, 2, 5, 5}
Output: 2
Explanation: 
Since 2 occurs once, while
other numbers occur twice, 
2 is the answer.
Example 2:
Input:
N = 7
A = {2, 2, 5, 5, 20, 30, 30}
Output: 20
Explanation:
Since 20 occurs once, while
other numbers occur twice, 
20 is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function search() which takes two arguments(array A and integer N) and returns the number occurring only once.
Expected Time Complexity: O(Log(N)).
Expected Auxiliary Space: O(1).
Constraints
0 <   N  <= 10^6
0 <= A[i] <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3
class Solution:
    def search(self, A, N):
        # your code here

Solutions:
class Solution:

	def search(self, A, N):
		for i in range(0, N, 2):
			if i == N - 1:
				return A[i]
			if A[i] != A[i + 1]:
				return A[i]
		return 0


class Solution:

	def search(self, A, N):
		(l, r) = (0, N - 1)
		while l <= r:
			mid = l + (r - l) // 2
			if mid % 2 == 0:
				if mid < N - 1 and A[mid] == A[mid + 1]:
					l = mid + 2
				elif mid > 0 and A[mid] == A[mid - 1]:
					r = mid - 2
				else:
					return A[mid]
			elif mid > 0 and A[mid] == A[mid - 1]:
				l = mid + 1
			elif mid < N - 1 and A[mid] == A[mid + 1]:
				r = mid - 1
			else:
				return A[mid]


class Solution:

	def search(self, A, N):
		left = 0
		right = N - 1
		while left < right:
			mid = (left + right) // 2
			if mid % 2 != 0:
				if A[mid] != A[mid - 1] and A[mid] != A[mid + 1]:
					return A[mid]
				elif A[mid] != A[mid - 1]:
					right = mid - 1
				else:
					left = mid + 1
			elif A[mid] != A[mid - 1] and A[mid] != A[mid + 1]:
				return A[mid]
			elif A[mid] != A[mid - 1]:
				left = mid + 1
			else:
				right = mid - 1
		return A[left]


class Solution:

	def search(self, A, N):
		x = 0
		for i in A:
			x ^= i
		return x


class Solution:

	def search(self, A, N):
		count = {}
		for i in A:
			if i in count.keys():
				count[i] = count[i] + 1
			else:
				count[i] = 1
		for (key, value) in count.items():
			if value == 1:
				return key


class Solution:

	def search(self, A, N):
		d = {}
		for i in A:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		lst = list(d.values())
		lst1 = list(d.keys())
		for i in range(len(lst)):
			if lst[i] == 1:
				return lst1[i]


class Solution:

	def search(self, A, N):
		res = 0
		for i in range(N):
			res = res ^ A[i]
		return res


class Solution:

	def search(self, A, N):
		xor = 0
		for i in range(len(A)):
			xor = xor ^ arr[i]
		return xor


class Solution:

	def search(self, A, N):
		ans = 0
		for val in A:
			ans ^= val
		return ans


class Solution:

	def search(self, A, N):
		dct = {}
		for i in A:
			if i in dct:
				dct[i] += 1
			else:
				dct[i] = 1
		output = []
		for i in dct:
			if dct[i] == 1:
				output.append(i)
		result = ','.join((str(i) for i in output))
		return result


class Solution:

	def search(self, A, N):
		i = 0
		while i < N - 1:
			if arr[i] != arr[i - 1] and arr[i] != arr[i + 1]:
				return arr[i]
			i += 1
		return arr[N - 1]


class Solution:

	def search(self, A, N):
		i = 0
		while i < N - 1:
			if A[i] == A[i + 1]:
				i += 2
			else:
				return A[i]
		return A[-1]


class Solution:

	def search(self, A, N):
		d = {}
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if d[i] == 1:
				return i


class Solution:

	def search(self, A, N):
		has = {}
		for a in A:
			if a in has:
				has[a] += 1
			else:
				has[a] = 1
		for key in has:
			if has[key] == 1:
				return key


class Solution:

	def search(self, A, N):
		m = {}
		for x in A:
			if x not in m:
				m[x] = 1
			else:
				m[x] += 1
		for (key, value) in m.items():
			if value == 1:
				return key


class Solution:

	def search(self, A, N):
		dict1 = {}
		for ele in A:
			if ele in dict1:
				dict1[ele] += 1
			else:
				dict1[ele] = 1
		for (k, v) in dict1.items():
			if v == 1:
				return k


class Solution:

	def search(self, A, N):
		hashmap = {}
		for i in A:
			hashmap[i] = 1 + hashmap.get(i, 0)
		for (key, value) in hashmap.items():
			if value == 1:
				return key


class Solution:

	def search(self, A, N):
		out = 0
		for ele in A:
			out ^= ele
		return out


class Solution:

	def search(self, A, N):
		xor = 0
		for num in A:
			xor ^= num
		return xor


class Solution:

	def search(self, A, N):
		a = set(A)
		suma = sum(A)
		sums = sum(a)
		return 2 * sums - suma


class Solution:

	def search(self, a, N):
		zero = 0
		one = 1
		while zero < N:
			if one < N and a[zero] == a[one]:
				zero += 2
				one += 2
			else:
				return a[zero]


class Solution:

	def search(self, A, N):
		n = len(A)
		if n == 1:
			return A[0]
		count = {}
		for i in range(n):
			count[A[i]] = 1 + count.get(A[i], 0)
		for (key, value) in count.items():
			if value == 1:
				return key


class Solution:

	def search(self, A, N):
		marker = -1
		for i in A:
			if marker == -1:
				marker = i
			elif marker == i:
				marker = -1
			elif marker != -1 and marker != i:
				return marker
		return marker


class Solution:

	def search(self, A, N):
		from collections import Counter
		res = Counter(A)
		for (k, v) in res.items():
			if v == 1:
				return k


class Solution:

	def search(self, A, N):
		xor = 0
		for e in arr:
			xor = xor ^ e
		return xor


class Solution:

	def search(self, A, N):
		d = {}
		for i in A:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		k = [[d[i], i] for i in d]
		k.sort()
		if k[0][0] == 1:
			return k[0][1]


class Solution:

	def search(self, A, N):
		sum1 = sum(A)
		sum2 = sum(set(A))
		return 2 * sum2 - sum1


class Solution:

	def search(self, a, n):
		for i in range(0, n, 2):
			if i + 1 < n:
				if a[i] != a[i + 1]:
					return a[i]
			else:
				return a[i]


class Solution:

	def search(self, A, N):
		ans = int(0)
		for x in A:
			ans = ans ^ x
		return ans


class Solution:

	def search(self, arr, n):
		res = 0
		XOR = 0
		for i in range(0, n):
			res = res ^ arr[i]
		return res


class Solution:

	def search(self, A, N):
		counter = {}
		for val in A:
			if val not in counter:
				counter[val] = 1
			else:
				counter[val] += 1
		for val in counter:
			if counter[val] == 1:
				return val
		return -1


from collections import defaultdict

class Solution:

	def search(self, A, N):
		xor = 0
		for i in range(N):
			xor = xor ^ A[i]
		return xor


from collections import defaultdict

class Solution:

	def search(self, A, N):
		mp = defaultdict(lambda : 0)
		for i in range(N):
			mp[A[i]] += 1
		for i in range(N):
			if mp[A[i]] == 1:
				return A[i]


class Solution:

	def search(self, arr, n):
		b = []
		sum1 = sum(arr)
		b = set(arr)
		sum2 = sum(b)
		return 2 * sum2 - sum1


class Solution:

	def search(self, A, N):
		sum = 0
		sum1 = 0
		for i in range(0, N):
			sum += A[i]
		s = set(A)
		for i in s:
			sum1 += i
		res = 2 * sum1 - sum
		return res


class Solution:

	def search(self, A, N):

		def helper(A, low, high):
			if low > high:
				return None
			if low == high:
				return A[low]
			m = low + (high - low) // 2
			if m % 2 == 0:
				if A[m] == A[m + 1]:
					return helper(A, m + 2, high)
				else:
					return helper(A, low, m)
			elif A[m] == A[m - 1]:
				return helper(A, m + 1, high)
			else:
				return helper(A, low, m - 1)
		return helper(A, 0, N - 1)


class Solution:

	def search(self, A, N):
		ans = []
		for i in range(0, N):
			if A[i] not in ans:
				ans.append(A[i])
			else:
				ans.remove(A[i])
		return ans[0]


class Solution:

	def search(self, A, N):
		d = {}
		ans = -1
		maxi = 0
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if d[i] == 1:
				return i
		else:
			return -1


class Solution:

	def search(self, A, N):
		XOR = arr[0]
		for i in range(1, N):
			XOR = XOR ^ arr[i]
		return XOR


class Solution:

	def search(self, A, N):
		N = len(A)
		low = 0
		high = N - 1
		while low < high:
			mid = low + high >> 1
			if mid % 2 != 0:
				if A[mid] == A[mid - 1]:
					low = mid + 1
				else:
					high = mid - 1
			elif A[mid] == A[mid + 1]:
				low = mid + 1
			else:
				high = mid
		return A[low]


class Solution:

	def search(self, A, N):
		d = {}
		for i in A:
			if i not in d:
				d[i] = 1
			else:
				d[i] = d[i] + 1
		for (key, value) in d.items():
			if d[key] == 1:
				return key


class Solution(object):

	def search1(self, nums, N):
		index = 0
		while index < N:
			if index + 1 < N and nums[index] == nums[index + 1]:
				index += 2
			else:
				break
		return nums[index]

	def search(self, nums, N):
		xor = 0
		for num in nums:
			xor ^= num
		return xor


class Solution:

	def search(self, nums, N):
		index = 0
		while index < N:
			if index + 1 < N and nums[index] == nums[index + 1]:
				index += 2
			else:
				break
		return nums[index]


class Solution:

	def search(self, A, N):
		ans = A[0]
		for i in range(1, N):
			ans = ans ^ A[i]
		return ans


class Solution:

	def search(self, A, N):
		l = 0
		h = N - 1
		while l <= h:
			mid = (h + l) // 2
			if A.count(A[mid]) == 1:
				return A[mid]
			elif A[mid] == A[mid - 1] and mid % 2 == 0:
				h = mid - 1
			elif A[mid] == A[mid - 1] and mid % 2 != 0:
				l = mid + 1
			elif A[mid] == A[mid + 1] and mid % 2 != 0:
				h = mid - 1
			elif A[mid] == A[mid + 1] and mid % 2 == 0:
				l = mid + 1


class Solution:

	def search(self, A, N):
		from collections import Counter
		d = Counter(A)
		for i in d:
			if d[i] == 1:
				return i
		return -1


class Solution:

	def search(self, A, N):
		import collections
		d1 = collections.Counter(A)
		for (i, j) in d1.items():
			if j == 1:
				return i


class Solution:

	def search(self, A, N):
		dic = {}
		for i in A:
			dic[i] = dic.get(i, 0) + 1
		for i in A:
			if dic[i] == 1:
				return i


from functools import reduce

class Solution:

	def search(self, A, N):
		return reduce(lambda x, y: x ^ y, A)


import collections

class Solution:

	def search(self, A, N):
		dict1 = collections.Counter(A)
		for i in A:
			if dict1[i] == 1:
				return i


class Solution:

	def search(self, A, N):
		i = 0
		j = 1
		c = 0
		if N == 1 or A[i] != A[j]:
			return A[i]
		if A[N - 1] != A[N - 2]:
			return A[N - 1]
		while j < N:
			if A[i] == A[j]:
				i += 1
				j += 1
				c = 0
			else:
				c += 1
				if c == 2:
					ans = A[i]
					break
				i += 1
				j += 1
		return ans


class Solution:

	def bs(self, arr, low, high):
		if low == high:
			return arr[low]
		mid = (low + high) // 2
		if mid % 2 == 0:
			if arr[mid] == arr[mid + 1]:
				return self.bs(arr, mid + 2, high)
			else:
				return self.bs(arr, low, mid)
		elif arr[mid] == arr[mid - 1]:
			return self.bs(arr, mid + 1, high)
		else:
			return self.bs(arr, low, mid - 1)

	def search(self, arr, n):
		return self.bs(arr, 0, n - 1)


class Solution:

	def search(self, A, n):
		i = A[0]
		for j in A[1:]:
			i = i ^ j
		return i


class Solution:

	def search(self, A, n):
		(i, x) = (0, 1)
		while x < n:
			if i != x and A[i] ^ A[x] == 0:
				i = x + 1
			x += 1
		return A[i]


class Solution:

	def search(self, A, N):
		xor1 = 0
		for i in range(len(A)):
			xor1 = xor1 ^ A[i]
		return xor1


class Solution:

	def search(self, A, N):
		start = 0
		end = N - 1
		while start < end:
			mid = (end + start) // 2
			if mid % 2 == 1:
				mid -= 1
			if A[mid] == A[mid + 1]:
				start = mid + 2
			else:
				end = mid
		return A[start]


from collections import Counter

class Solution:

	def search(self, A, N):
		counter = Counter(A).most_common()
		return counter[-1][0]


class Solution:

	def search(self, A, N):
		j = {}
		u = []
		e = list(set(A))
		for x in e:
			j[x] = 0
		for x in A:
			j[x] = j[x] + 1
		for x in e:
			if j[x] != 2:
				return x
				break


class Solution:

	def search(self, A, N):
		d = {}
		for i in A:
			d[i] = d.get(i, 0) + 1
		for (k, v) in d.items():
			if v == 1:
				return k