Given an array of N positive integers where all numbers occur even number of times except one number which occurs odd number of times. Find the exceptional number.
Example 1:
Input:
N = 7
Arr[] = {1, 2, 3, 2, 3, 1, 3}
Output: 3
Explaination: 3 occurs three times.
Example 2:
Input:
N = 7
Arr[] = {5, 7, 2, 7, 5, 2, 5}
Output: 5
Explaination: 5 occurs three times.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getOddOccurrence() which takes arr[] and n as input parameters and returns the exceptional number.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def getOddOccurrence(self, arr, n):

        # code here 

Solutions:
class Solution:

	def getOddOccurrence(self, arr, n):
		result = 0
		for i in range(n):
			result = result ^ arr[i]
		return result


class Solution:

	def getOddOccurrence(self, arr, n):
		res = 0
		for i in arr:
			res ^= i
		return res


class Solution:

	def getOddOccurrence(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		for i in range(n):
			if dic[arr[i]] % 2 != 0:
				return arr[i]


class Solution:

	def getOddOccurrence(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in arr:
			if d[i] % 2 != 0:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		res = dict()
		for i in arr:
			if i in res:
				res[i] += 1
			else:
				res[i] = 1
		for j in res:
			if res[j] % 2 != 0:
				return j


class Solution:

	def getOddOccurrence(self, arr, n):
		xor_ = 0
		for ele in arr:
			xor_ ^= ele
		return xor_


from collections import Counter

class Solution:

	def getOddOccurrence(self, arr, n):
		e = Counter(arr)
		for j in e:
			if e[j] % 2 != 0:
				return j


class Solution:

	def getOddOccurrence(self, arr, n):
		exceptional_number = 0
		for num in arr:
			exceptional_number ^= num
		return exceptional_number


class Solution:

	def getOddOccurrence(self, arr, n):
		mask = 0
		for e in arr:
			mask ^= e
		return mask


class Solution:

	def getOddOccurrence(self, arr, n):
		x = 0
		arr.sort()
		for i in arr:
			x = x ^ i
		return x


class Solution:

	def getOddOccurrence(self, arr, n):
		dict1 = {}
		for i in range(n):
			dict1[arr[i]] = dict1.get(arr[i], 0) + 1
		for key in dict1.keys():
			if dict1[key] % 2 == 1:
				return key


class Solution:

	def getOddOccurrence(self, arr, n):
		freq = {}
		for i in arr:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		for i in freq:
			if freq[i] % 2 != 0:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		l = {}
		for i in arr:
			l[i] = l.get(i, 0) + 1
		for (key, value) in l.items():
			if value % 2 != 0:
				return key


from collections import Counter

class Solution:

	def getOddOccurrence(self, arr, n):
		dc = Counter(arr)
		for key in dc:
			if dc[key] % 2 != 0:
				return key


import collections

class Solution:

	def getOddOccurrence(self, arr, n):
		dict1 = collections.Counter(arr)
		for i in dict1:
			if dict1[i] % 2 != 0:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		dict = {}
		for i in range(n):
			if arr[i] not in dict:
				dict[arr[i]] = 1
			else:
				dict[arr[i]] += 1
		for key in dict:
			if dict[key] % 2 == 1:
				return key


class Solution:

	def getOddOccurrence(self, arr, n):
		a = arr[0]
		for i in range(1, n):
			a = a ^ arr[i]
		return a


class Solution:

	def getOddOccurrence(self, arr, n):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for (num, count) in dic.items():
			if count % 2 != 0:
				return num


from collections import Counter

class Solution:

	def getOddOccurrence(self, arr, n):
		freq = Counter(arr)
		x = list(freq.keys())
		y = list(freq.values())
		for i in range(len(y)):
			if y[i] % 2 != 0:
				return x[i]


class Solution:

	def getOddOccurrence(self, arr, n):
		count = {}
		for i in arr:
			if i in count:
				count[i] += 1
			else:
				count[i] = 1
		for i in count:
			if count[i] % 2 == 1:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for i in arr:
			if dic[i] % 2 == 1:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		odd = 0
		A = {}
		for i in range(n):
			A[arr[i]] = A.get(arr[i], 0) + 1
		for i in range(n):
			if A[arr[i]] % 2 != 0:
				return arr[i]


class Solution:

	def getOddOccurrence(self, arr, n):
		diction = {}
		for i in arr:
			if i in diction:
				diction[i] += 1
			else:
				diction[i] = 1
		for (key, value) in diction.items():
			if value % 2 != 0:
				return key


from collections import Counter

class Solution:

	def getOddOccurrence(self, arr, n):
		c = Counter(arr)
		for (key, values) in c.items():
			if values % 2 != 0:
				return key


class Solution:

	def getOddOccurrence(self, arr, n):
		from collections import Counter
		arr = Counter(arr)
		for i in arr:
			if arr[i] % 2:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		table = {}
		digit = 0
		for i in arr:
			if i in table:
				table[i] += 1
			else:
				table[i] = 1
		for j in table:
			if table[j] % 2 != 0:
				return j
		return digit


class Solution:

	def getOddOccurrence(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d.keys():
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		for key in d.keys():
			if d[key] % 2 == 1:
				return key


class Solution:

	def getOddOccurrence(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for j in d:
			if d[j] % 2 == 1:
				return j


from collections import Counter

class Solution:

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


class Solution:

	def getOddOccurrence(self, nums, n):
		d = {}
		for i in nums:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (i, j) in d.items():
			if j % 2 != 0:
				return i
				break


class Solution:

	def getOddOccurrence(self, arr, n):
		d = {}
		l = []
		k = []
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d.keys():
			k.append(i)
		for i in d.values():
			l.append(i)
		for i in range(len(l)):
			if l[i] % 2 != 0:
				return k[i]
				break


class Solution:

	def getOddOccurrence(self, arr, n):
		test = {}
		for i in range(0, n):
			if arr[i] in test.keys():
				test[arr[i]] += 1
			if arr[i] not in test.keys():
				test[arr[i]] = 1
		key = test.keys()
		for i in key:
			if test[i] % 2 != 0:
				return i


class Solution:

	def getOddOccurrence(self, arr, n):
		dic = dict()
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for (k, v) in dic.items():
			if v % 2 != 0:
				return k