Given a sorted array arr[] of size N. Find the element that appears only once in the array. All other elements appear exactly twice. 
Example 1:
Input:
N = 11
arr[] = {1, 1, 2, 2, 3, 3, 4, 50, 50, 65, 65}
Output: 4
Explanation: 4 is the only element that 
appears exactly once.
 
Your Task:  
You don't need to read input or print anything. Complete the function findOnce() which takes sorted array and its size as its input parameter and returns the element that appears only once. 
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
-10^{5} <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Divide and conquer

Complete search

Starter code: #User function Template for python3

class Solution:
    def findOnce(self,arr : list, n : int):
        # Complete this function

Solutions:
from collections import Counter

class Solution:

	def findOnce(self, arr: list, n: int):
		a = Counter(arr)
		for (k, v) in a.items():
			if v == 1:
				return k


class Solution:

	def findOnce(self, arr: list, n: int):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		d1 = {}
		i = 0
		if n == 1:
			return arr[0]
		while i != n - 1:
			if arr[i] in d1:
				d1[arr[i]] += 1
				i += 1
			else:
				d1[arr[i]] = 1
				if arr[i + 1] != arr[i]:
					return arr[i]
				i += 2
		return arr[n - 1]


class Solution:

	def findOnce(self, arr: list, n: int):
		(left, right) = (0, n - 1)
		while left < right:
			mid = int((left + right) / 2)
			if mid % 2 == 1 and arr[mid - 1] == arr[mid] or (mid % 2 == 0 and arr[mid] == arr[mid + 1]):
				left = mid + 1
			else:
				right = mid
		return arr[left]


def search(arr, low, high):
	if low > high:
		return None
	if low == high:
		return arr[low]
	mid = low + (high - low) // 2
	if mid % 2 == 0:
		if arr[mid] == arr[mid + 1]:
			return search(arr, mid + 2, high)
		else:
			return search(arr, low, mid)
	elif arr[mid] == arr[mid - 1]:
		return search(arr, mid + 1, high)
	else:
		return search(arr, low, mid - 1)

class Solution:

	def findOnce(self, arr: list, n: int):
		ans = search(arr, 0, n - 1)
		return ans


class Solution:

	def findOnce(self, arr: list, n: int):
		r = 0
		while r < n - 1:
			if arr[r] != arr[r + 1]:
				return arr[r]
			r += 2
		return arr[n - 1]


class Solution:

	def findOnce(self, arr: list, n: int):
		dict = {}
		for i in arr:
			dict[i] = dict.get(i, 0) + 1
		for (key, value) in dict.items():
			if value == 1:
				return key


class Solution:

	def findOnce(self, arr: list, n: int):
		low = 0
		high = len(arr) - 1

		def findOnce(arr, low, high):
			mid = low + (high - low) // 2
			if low > high:
				return -1
			if low == high:
				return arr[low]
			if mid % 2 == 0:
				if arr[mid] == arr[mid + 1]:
					return findOnce(arr, mid + 2, high)
				else:
					return findOnce(arr, low, mid)
			elif arr[mid] != arr[mid + 1]:
				return findOnce(arr, mid + 1, high)
			else:
				return findOnce(arr, low, mid - 1)
		return findOnce(arr, low, high)


class Solution:

	def findOnce(self, arr: list, n: int):
		hashA = {}
		for a in arr:
			if not a in hashA:
				hashA[a] = 1
			else:
				hashA[a] += 1
		for (k, v) in hashA.items():
			if v == 1:
				return k


class Solution:

	def findOnce(self, arr: list, n: int):
		if n == 1:
			return arr[0]
		(start, end) = (0, n - 1)
		while start <= end:
			mid = (start + end) // 2
			if mid == 0 or mid == n - 1 or (arr[mid] != arr[mid - 1] and arr[mid] != arr[mid + 1]):
				return arr[mid]
			if mid % 2 == 0:
				if arr[mid] == arr[mid + 1]:
					start = mid + 2
				else:
					end = mid - 2
			elif arr[mid] == arr[mid - 1]:
				start = mid + 1
			else:
				end = mid - 1
		return -1


class Solution:

	def findOnce(self, arr: list, n: int):
		if n == 1:
			return arr[0]
		for i in range(1, n, 2):
			if arr[i] != arr[i - 1]:
				return arr[i - 1]
		return arr[i + 1]


class Solution:

	def findOnce(self, arr: list, n: int):
		l = 0
		h = n - 1
		if l == h:
			return arr[l]
		if arr[0] < arr[1]:
			return arr[0]
		if arr[n - 1] > arr[n - 2]:
			return arr[n - 1]
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] < arr[mid + 1] and arr[mid] > arr[mid - 1]:
				return arr[mid]
			elif arr[mid - 1] == arr[mid]:
				if mid % 2 == 1:
					l = mid + 1
				else:
					h = mid - 1
			elif arr[mid] == arr[mid + 1]:
				if mid % 2 == 1:
					h = mid - 1
				else:
					l = mid + 1
		return -1


class Solution:

	def findOnce(self, arr: list, n: int):
		dict1 = {}
		for i in arr:
			if i not in dict1:
				dict1[i] = 0
			dict1[i] += 1
		for i in dict1:
			if dict1[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		dict = {}
		for i in arr:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		value = {i for i in dict if dict[i] == 1}
		a = list(value)
		return a[0]


class Solution:

	def findOnce(self, arr: list, n: int):
		res = 0
		for i in range(0, n):
			res = arr[i] ^ res
		return res


class Solution:

	def findOnce(self, arr: list, n: int):
		counts = {}
		for i in arr:
			counts[i] = counts.get(i, 0) + 1
		for i in arr:
			if counts[i] == 1:
				return i
		return -1


class Solution:

	def findOnce(self, arr: list, n: int):
		l = 0
		r = len(arr) - 1
		while l <= r:
			mid = l + (r - l) // 2
			if (mid - 1 < 0 or arr[mid] != arr[mid - 1]) and (mid + 1 == len(arr) or arr[mid] != arr[mid + 1]):
				return arr[mid]
			leftside = mid - 1 if arr[mid - 1] == arr[mid] else mid
			if leftside % 2 == 1:
				r = mid - 1
			else:
				l = mid + 1


class Solution:

	def findOnce(self, arr: list, n: int):
		arr.append(0)
		i = 0
		while i < n:
			if arr[i] == arr[i + 1]:
				i += 2
			else:
				return arr[i]
				break


class Solution:

	def findOnce(self, arr: list, n: int):
		from collections import Counter
		ans = Counter(arr)
		for i in ans:
			if ans[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for (k, v) in d.items():
			if v == 1:
				return k


class Solution:

	def findOnce(self, arr: list, n: int):
		xor = 0
		for i in arr:
			xor = xor ^ i
		return xor


class Solution:

	def findOnce(self, arr: list, n: int):
		x = arr[0]
		for i in range(1, len(arr)):
			x ^= arr[i]
		return x


class Solution:

	def findOnce(self, arr: list, n: int):
		if len(arr) == 1:
			return arr[0]
		i = 0
		while i + 1 <= n - 1:
			if arr[i] != arr[i + 1]:
				return arr[i]
			i += 2
		if i <= n - 1:
			if arr[i] != arr[i - 1]:
				return arr[i]


class Solution:

	def findOnce(self, arr: list, n: int):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for i in arr:
			if i in dic and dic[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		for (i, item) in enumerate(arr):
			if i == 0 and n > 1 and (arr[i] != arr[i + 1]):
				return item
			if i > 0 and i == n - 1 and (arr[i - 1] != item):
				return item
			if i > 0 and i < n - 1 and (arr[i - 1] != arr[i]) and (arr[i + 1] != arr[i]):
				return item
		return arr[0]


class Solution:

	def findOnce(self, nums: list, n: int):
		i = 0
		j = n - 2
		if n == 1:
			return arr[0]
		if arr[n - 1] != arr[n - 2]:
			return arr[n - 1]
		while i <= j:
			mid = (i + j) // 2
			if mid % 2 == 0:
				if nums[mid] != nums[mid + 1]:
					j = mid - 1
				else:
					i = mid + 1
			elif nums[mid] == nums[mid + 1]:
				j = mid - 1
			else:
				i = mid + 1
		return nums[i]


class Solution:

	def findOnce(self, arr: list, n: int):
		dict = {}
		for i in arr:
			if not dict.get(i):
				dict[i] = 1
			else:
				dict[i] += 1
		for (i, j) in dict.items():
			if j == 1:
				return i


class Solution:

	def findOnce(self, l: list, n: int):
		c = 0
		if len(l) == 1:
			return l[0]
		else:
			for i in range(0, len(l) - 1, 2):
				if l[i] != l[i + 1]:
					c += 1
					return l[i]
					break
		if c == 0 and len(l) % 2 != 0:
			return l[n - 1]


class Solution(object):

	def findOnce1(self, nums: list, n: int):
		result = nums[0]
		for num in nums[1:]:
			result ^= num
		return result

	def findOnce(self, nums: list, n: int):
		(left, right) = (0, n - 1)
		while left < right:
			mid = (left + right) // 2
			halvesAreEven = (right - mid) % 2 == 0
			if nums[mid] == nums[mid + 1]:
				if halvesAreEven:
					left = mid + 2
				else:
					right = mid - 1
			elif nums[mid] == nums[mid - 1]:
				if halvesAreEven:
					right = mid - 2
				else:
					left = mid + 1
			else:
				return nums[mid]
		return nums[left]


class Solution(object):

	def findOnce(self, nums: list, n: int):
		result = nums[0]
		for num in nums[1:]:
			result ^= num
		return result


class Solution:

	def findOnce(self, arr: list, n: int):
		arr.sort()
		a = arr[0::2]
		b = arr[1::2]
		return sum(a) - sum(b)


class Solution:

	def findOnce(self, A: list, n: int):
		(low, high) = (0, n - 1)
		while low < high:
			mid = (low + high) // 2
			if mid == 0:
				return A[0]
			if mid == n - 1:
				return A[n - 1]
			if A[mid] != A[mid - 1] and A[mid] != A[mid + 1]:
				return A[mid]
			if mid % 2 == 1:
				if A[mid] == A[mid - 1]:
					low = mid + 1
				else:
					high = mid - 1
			elif A[mid] == A[mid - 1]:
				high = mid - 2
			else:
				low = mid + 1
		return A[low]


class Solution:

	def findOnce(self, arr: list, n: int):
		lastitem = arr[0]
		count = 1
		for item in arr[1:]:
			if lastitem == item:
				count += 1
			else:
				if count == 1:
					return lastitem
				lastitem = item
				count = 1
		return lastitem


from collections import Counter

class Solution:

	def findOnce(self, arr: list, n: int):
		d = dict(Counter(arr))
		for i in d.keys():
			if d[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		d = {}
		for i in arr:
			d[i] = 0
		for i in arr:
			d[i] = d[i] + 1
		for i in d:
			if d[i] == 1:
				return i


class Solution:

	def findOnce(self, arr: list, n: int):
		mydict = dict()
		for i in range(n):
			if arr[i] not in mydict:
				mydict[arr[i]] = 1
			else:
				mydict[arr[i]] += 1
		for (key, val) in mydict.items():
			if val == 1:
				return key


class Solution:

	def findOnce(self, arr: list, n: int):
		from collections import Counter
		a = Counter(arr)
		for (i, j) in a.items():
			if j == 1:
				return i


class Solution:

	def findOnce(self, nums: list, n: int):
		low = 0
		high = len(nums) - 2
		while low <= high:
			mid = low + high >> 1
			if nums[mid] == nums[mid ^ 1]:
				low = mid + 1
			else:
				high = mid - 1
		return nums[low]


class Solution:

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


from collections import Counter

class Solution:

	def findOnce(self, arr: list, n: int):
		l = len(arr)
		data = Counter(arr)
		ex = dict(data)
		for (k, v) in ex.items():
			if v == 1:
				return k


class Solution:

	def findOnce(self, arr: list, n: int):
		c = 2 * sum(set(arr)) - sum(arr)
		return c


class Solution:

	def findOnce(self, a: list, n: int):
		k = 0
		for ele in a:
			k = k ^ ele
		return k


class Solution:

	def findOnce(self, arr: list, n: int):
		lo = 0
		hi = n - 1
		if n == 1:
			return arr[0]
		while lo <= hi:
			mid = (lo + hi) // 2
			if mid != 0 and arr[mid] == arr[mid - 1]:
				if mid % 2:
					lo = mid + 1
				else:
					hi = mid - 2
			elif mid != n - 1 and arr[mid] == arr[mid + 1]:
				if mid % 2:
					hi = mid - 1
				else:
					lo = mid + 2
			else:
				return arr[mid]


class Solution:

	def findOnce(self, arr: list, n: int):
		d = {}
		for ele in arr:
			if ele in d:
				d[ele] += 1
			else:
				d[ele] = 1
		f = 0
		for (k, v) in d.items():
			if v == 1:
				f = k
			else:
				continue
		return f