Given an array of integers arr[] of length N, every element appears thrice except for one which occurs once.
Find that element which occurs once.
Example 1:
Input:
N = 4
arr[] = {1, 10, 1, 1}
Output:
10
Explanation:
10 occurs once in the array while the other
element 1 occurs thrice.
Example 2:
Input:
N = 10
arr[] = {3, 2, 1, 34, 34, 1, 2, 34, 2, 1}
Output:
3
Explanation:
All elements except 3 occurs thrice in the array.
 
Your Task:
The task is to complete the function singleElement() which finds and returns the element occuring once in the array.
Constraints:
1 ≤ N ≤ 10^{6}
-10^{9} ≤ A[i] ≤ 10^{9}
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def singleElement(self, arr, N):

        # code here 

Solutions:
from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		c = Counter(arr)
		for i in c:
			if c[i] == 1:
				return i


class Solution:

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


class Solution:

	def singleElement(self, arr, N):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for key in dic:
			if dic[key] == 1:
				return key


class Solution:

	def singleElement(self, arr, N):
		ones = 0
		twos = 0
		for x in arr:
			ones = (ones ^ x) & ~twos
			twos = (twos ^ x) & ~ones
		return ones


class Solution:

	def singleElement(self, arr, N):
		count = {}
		for num in arr:
			count[num] = count.get(num, 0) + 1
		for num in count:
			if count[num] != 3:
				return num


class Solution:

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


class Solution:

	def singleElement(self, arr, N):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for (i, j) in d.items():
			if j == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		ones = 0
		twos = 0
		for i in range(N):
			current = arr[i]
			twos |= ones & current
			ones ^= current
			common = ones & twos
			ones &= ~common
			twos &= ~common
		return ones


class Solution:

	def singleElement(self, arr, N):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] = d[i] + 1
		for key in d.keys():
			if d[key] != 3:
				return key


class Solution:

	def singleElement(self, arr, N):
		a = {}
		for i in arr:
			if i in a:
				a[i] += 1
			else:
				a[i] = 1
		for j in arr:
			if a[j] <= 1:
				return j


class Solution:

	def singleElement(self, arr, N):
		map = {}
		for i in arr:
			if i in map:
				map[i] += 1
			else:
				map[i] = 1
		for (i, j) in map.items():
			if j == 1:
				return i


from collections import defaultdict

class Solution:

	def singleElement(self, arr, N):
		cnts = defaultdict(int)
		for num in arr:
			cnts[num] += 1
		for (num, cnt) in cnts.items():
			if cnt == 1:
				return num


class Solution:

	def singleElement(self, arr, N):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for i in d:
			if d.get(i) != 3:
				return i


class Solution:

	def singleElement(self, arr, N):
		D = {}
		for i in arr:
			D[i] = D.get(i, 0) + 1
		for i in D:
			if D.get(i) == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		(a, b, c) = (-1, 0, 0)
		for r in arr:
			(a1, b1, c1) = (a & r, b & r, c & r)
			(a, b, c) = (a ^ a1, b ^ b1, c ^ c1)
			(a, b, c) = (a | c1, b | a1, c | b1)
		return b


class Solution:

	def singleElement(self, a, n):
		d = {}
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		for i in d.keys():
			if d[i] == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		return (3 * sum(set(arr)) - sum(arr)) // 2


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		c = Counter(arr)
		for (item, count) in c.items():
			if count == 1:
				return item


class Solution:

	def singleElement(self, arr, N):
		d = dict()
		for ele in arr:
			d[ele] = 0
		for ele in arr:
			d[ele] = d[ele] + 1
		for ele in d.keys():
			if d[ele] == 1:
				return ele


class Solution:

	def singleElement(self, arr, N):
		return (3 * sum(set(arr)) - sum(arr)) // 2
		sums = [0] * 32
		for a in arr:
			for i in range(32):
				if a >> i & 1:
					sums[i] = (sums[i] + 1) % 3
		output = 0
		for (i, b) in enumerate(sums):
			if b:
				output += 1 << i
		return output


class Solution:

	def singleElement(self, arr, N):
		a = 0
		b = 0
		for i in range(N):
			b = b ^ a & arr[i]
			a = a ^ arr[i]
			common = ~(a & b)
			a = a & common
			b = b & common
		return a


class Solution:

	def singleElement(self, arr, N):
		count = 0
		arr.sort()
		for i in range(N - 1):
			if arr[i] != arr[i + 1] and count == 0:
				return arr[i]
			else:
				count += 1
			if arr[i] != arr[i + 1]:
				count = 0
		return arr[-1]


class Solution:

	def singleElement(self, arr, N):
		p = {}
		for i in arr:
			p[i] = 0
		for i in range(N):
			p[arr[i]] += 1
		for i in p:
			if p[i] == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (k, v) in d.items():
			if v == 1:
				return k


class Solution:

	def singleElement(self, arr, N):
		arr.sort()
		for i in arr:
			if arr.count(i) == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		arr = sorted(arr)
		for i in range(len(arr)):
			count = arr.count(arr[i])
			if count == 1:
				return arr[i]


class Solution:

	def singleElement(self, arr, N):
		g = {}
		for i in range(0, N):
			c = arr[i]
			if c not in g:
				g[c] = 1
			else:
				g[c] = g[c] + 1
		for x in g:
			if g[x] == 1:
				return x


class Solution:

	def singleElement(self, arr, N):
		a = dict.fromkeys(arr, 0)
		for i in arr:
			a[i] += 1
		for j in a:
			if a[j] == 1:
				return j
				break


class Solution:

	def singleElement(self, nums, N):
		return (3 * sum(set(nums)) - sum(nums)) // 2


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		p = ''
		a = Counter(arr)
		for (k, v) in a.items():
			if v <= 2:
				p += str(k)
		return int(p)


class Solution:

	def singleElement(self, arr, N):
		d = {}
		ans = 0
		for i in arr:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
		for i in list(d.keys()):
			if d[i] == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		hm = {}
		for i in arr:
			if i not in hm:
				hm[i] = 0
			hm[i] += 1
		for (i, j) in hm.items():
			if j == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		h = {}
		for num in arr:
			h[num] = h.get(num, 0) + 1
		for key in h:
			if h[key] == 1:
				return key


class Solution:

	def singleElement(self, arr, N):
		arr.sort()
		for i in range(1, N, 3):
			if arr[i] != arr[i - 1]:
				return arr[i - 1]
		return arr[-1]


class Solution:

	def singleElement(self, arr, N):
		d = dict()
		for i in arr:
			m = 1
			if i in d.keys():
				m += d[i]
			d[i] = m
		for i in d.keys():
			if d[i] == 1:
				return i
		return 0


class Solution:

	def singleElement(self, arr, N):
		ones = twos = 0
		for i in range(N):
			twos |= ones & arr[i]
			ones ^= arr[i]
			comm = ~(ones & twos)
			ones &= comm
			twos &= comm
		return ones


class Solution:

	def singleElement(self, arr, N):
		one = 0
		two = 0
		for i in range(N):
			two = two ^ one & arr[i]
			one = one ^ arr[i]
			common = ~(one & two)
			one &= common
			two &= common
		return one


class Solution:

	def singleElement(self, arr, N):
		freq = {}
		for i in arr:
			freq[i] = freq.get(i, 0) + 1
		for (key, j) in freq.items():
			if j != 3:
				return key


class Solution:

	def singleElement(self, arr, N):
		sort = sorted(arr)
		if N == 1:
			return sort[0]
		if sort[0] != sort[1]:
			return sort[0]
		for i in range(1, N):
			if i == N - 1:
				return sort[i]
			if (sort[i - 1] != sort[i]) & (sort[i] != sort[i + 1]):
				return sort[i]


import math

class Solution:

	def singleElement(self, arr, n):
		three_n = 2 ** 32 - 1
		three_n1 = 0
		three_n2 = 0
		for i in range(n):
			temp = three_n & arr[i]
			temp1 = three_n1 & arr[i]
			temp2 = three_n2 & arr[i]
			three_n = temp ^ three_n ^ temp2
			three_n1 = temp1 ^ three_n1 ^ temp
			three_n2 = temp2 ^ three_n2 ^ temp1
		ans = three_n1
		if ans >= 2 ** 31:
			ans -= 2 ** 32
		return ans


class Solution:

	def singleElement(self, arr, N):
		sum1 = 0
		for i in arr:
			sum1 += i
		set1 = set(arr)
		set1 = sorted(set1)
		sum2 = 0
		for ele in set1:
			sum2 += ele
		return int(sum2 - (sum1 - sum2) / 2)


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		k = Counter(arr)
		minval = 0
		for (i, j) in k.items():
			if j == 1:
				minval = i
				break
			else:
				pass
		return minval


class Solution:

	def singleElement(self, arr, N):
		di = {}
		for i in arr:
			if i not in di:
				di[i] = 1
			else:
				di[i] += 1
		for (i, j) in di.items():
			if j == 1:
				return i


class Solution:

	def singleElement(self, arr, N):
		from collections import Counter
		freq = Counter(arr)
		for e in freq:
			if freq[e] == 1:
				return e


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		ht = Counter(arr)
		for (k, val) in ht.items():
			if val == 1:
				return k


class Solution:

	def singleElement(self, arr, N):
		seen = {}
		for x in arr:
			if x not in seen:
				seen[x] = 1
			else:
				seen[x] += 1
		singleelem = {value: key for (key, value) in seen.items()}
		return singleelem[1]


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		d = Counter(arr)
		a = list(d.keys())
		v = list(d.values())
		p = v.index(1)
		return a[p]


class Solution:

	def singleElement(self, arr, N):
		from collections import Counter
		a = Counter(arr)
		v = list(a.values())
		k = list(a.keys())
		for i in range(len(v)):
			if v[i] == 1:
				return k[i]


class Solution:

	def singleElement(self, arr, N):
		set1 = set(arr)
		z = sum(set1)
		result = (3 * z - sum(arr)) // 2
		return result


from collections import Counter

class Solution:

	def singleElement(self, arr, N):
		d = Counter(arr)
		k = list(d.keys())
		v = list(d.values())
		ps = v.index(1)
		return k[ps]