Given an array A[] of size N. Find the number of pairs (i, j) such that
A_{i }XOR A_{j} = 0, and 1 ≤ i < j ≤ N.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {1, 3, 4, 1, 4}
Output : 2
Explanation:
Index( 0, 3 ) and (2 , 4 ) are only pairs 
whose xors is zero so count is 2.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {2, 2, 2} 
Output :  3
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function calculate() that takes an array (arr), sizeOfArray (n), and return the count of Zeros Xor's Pairs. The driver code takes care of the printing.
Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(1).
Output:
For each test case, output a single integer i.e counts of Zeros Xors Pairs
Constraints
2 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Sorting

Data structures

Starter code: #User function Template for python3


def calculate (arr, n) : 
    #Complete the function



Solutions:
def calculate(arr, n):
	arr.sort()
	ans = 0
	count = 0
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			count += 1
		else:
			ans += count * (count + 1) // 2
			count = 0
	ans += count * (count + 1) // 2
	return ans


from itertools import combinations

def calculate(arr, n):
	comb = combinations(arr, 2)
	count = 0
	for i in comb:
		(x, y) = i
		if x ^ y == 0:
			count += 1
	return count


def calculate(arr, n):
	mp = {}
	for i in range(n):
		if arr[i] in mp:
			mp[arr[i]] += 1
		else:
			mp[arr[i]] = 1
	count = 0
	for i in mp:
		if mp[i] > 1:
			count += mp[i] * (mp[i] - 1) // 2
	return count


def calculate(arr, n):
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] ^ arr[j] == 0:
				c = c + 1
	return c


from collections import Counter

def calculate(arr, n):
	arr.sort()
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			a = arr[i] ^ arr[j]
			if a == 0:
				c = c + 1
	return c


def calculate(arr, n):
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			ele = arr[i] ^ arr[j]
			if ele == 0:
				count += 1
	return count


def calculate(arr, n):
	rec = Counter(arr)
	return sum((x * (x - 1) // 2 for x in rec.values()))
from collections import *


def calculate(arr, n):
	i = 0
	j = 1
	total = 0
	arr = sorted(arr)
	while j < len(arr):
		if not arr[i] ^ arr[j]:
			while j < len(arr) and (not arr[i] ^ arr[j]):
				count = j - i
				total = total + count
				j = j + 1
			i = j - 1
		else:
			j = j + 1
			i = i + 1
	return total


def calculate(arr, n):
	arr.sort()
	start = 0
	end = start + 1
	count = 0
	pairs = 0
	while start < n and end < n:
		while start < n and end < n and (arr[start] == arr[end]):
			count += 1
			end += 1
		pairs = pairs + count * (count + 1) // 2
		count = 0
		start = end
		end = end + 1
	return pairs


def calculate(arr, n):
	arr.sort()
	i = 0
	j = 1
	cnt = 0
	while i <= len(arr) - 2 and j <= len(arr) - 1:
		for k in range(j, len(arr)):
			if arr[i] ^ arr[k] == 0:
				cnt += 1
		i += 1
		j += 1
	return cnt


def calculate(arr, n):
	dic = {}
	count = 0
	for i in arr:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	for i in dic:
		count += dic[i] * (dic[i] - 1) // 2
	return count


def calculate(arr, n):
	if len(set(arr)) == n:
		return 0
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	s = 0
	for i in d:
		s += d[i] * (d[i] - 1) // 2
	return s


from collections import Counter

def calculate(arr, n):
	c = Counter(arr)
	count = 0
	for item in c.values():
		count += item * (item - 1) // 2
	return count


def calculate(arr, n):
	l = []
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] ^ arr[j] == 0:
				l.append((i, j))
	return len(l)


from itertools import combinations

def calculate(arr, n):
	z = combinations(arr, 2)
	c = 0
	for i in z:
		(x, y) = i
		if x ^ y == 0:
			c += 1
	return c


def calculate(arr, n):
	max1 = max(arr)
	freq = [0 for i in range(max1 + 1)]
	for i in arr:
		freq[i] += 1
	ans = 0
	for i in freq:
		ans = ans + i * (i - 1) // 2
	return ans


def calculate(arr, n):
	total = 0
	dic = {}
	for i in range(len(arr)):
		if arr[i] not in dic:
			dic[arr[i]] = 1
		else:
			dic[arr[i]] = dic[arr[i]] + 1
	for i in dic:
		total = total + dic[i] * (dic[i] - 1) // 2
	return total


def calculate(arr, n):
	count = 0
	d = dict()
	for x in arr:
		if d.get(x) == None:
			d[x] = 0
		count += d[x]
		d[x] += 1
	return count


def calculate(arr, n):
	d = dict()
	count = 0
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
		else:
			d[arr[i]] = d[arr[i]] + 1
	for i in d:
		count = count + d[i] * (d[i] - 1) // 2
	return count


def calculate(arr, n):
	i = 0
	j = n - 1
	c = 0
	while i < n - 1:
		if i == j:
			i += 1
			j = n - 1
		if arr[i] == arr[j]:
			c += 1
		j -= 1
	return c - 1


def calculate(arr, n):
	ans = 0
	d = {}
	for i in arr:
		d[i] = 1 + d.get(i, 0)
	for i in d:
		a = d[i]
		if a > 1:
			ans += a * (a - 1) // 2
	return ans


from math import *

def calculate(arr, n):
	dic = {}
	for i in arr:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	c = 0
	for (i, j) in dic.items():
		if j > 1:
			nu = factorial(j)
			du = factorial(j - 2)
			r = 2
			ans = nu // (r * du)
			c += ans
	return c


def calculate(arr, n):
	from collections import Counter
	mp = Counter(arr)
	res = list()
	ans = 0
	for (key, value) in mp.items():
		if value > 1:
			res.append(value)
	for i in range(len(res)):
		temp = res[i] * (res[i] - 1) // 2
		ans += temp
	return ans


def calculate(arr, n):
	cnt = 0
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] ^ arr[j] == 0:
				cnt += 1
	return cnt


def calculate(a, n):
	c = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[i] ^ a[j] == 0:
				c += 1
	return c


def calculate(arr, n):
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	cont = 0
	for (i, j) in d.items():
		if j > 1:
			cont += int(j * (j - 1) / 2)
	return cont


from collections import Counter

def calculate(arr, n):
	Res = 0
	Count = Counter(arr)
	for (K, V) in Count.items():
		if V >= 2:
			Res += V * (V - 1) // 2
	return Res


def calculate(arr, n):
	d = {}
	c = 0
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d.keys():
		a = d[i] * (d[i] - 1) // 2
		c += a
	return c


def calculate(a, n):
	a.sort()
	count = 1
	answer = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			count += 1
		else:
			answer = answer + count * (count - 1) // 2
			count = 1
	answer = answer + count * (count - 1) // 2
	return answer


from collections import Counter

def calculate(arr, n):
	s = Counter(arr)
	u = []
	c = 0
	for (x, y) in s.items():
		if y > 1:
			u.append(y)
	for i in range(len(u)):
		q = u[i] * (u[i] - 1) // 2
		c = c + q
	return c


def calculate(a, n):
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] ^ a[j] == 0:
				count += 1
	return count


def calculate(arr, n):
	arr.sort()
	count = 0
	for i in range(n):
		for j in range(1, n):
			if arr[i] - arr[j] == 0 and i < j:
				count += 1
	return count


def calculate(arr, n):
	arr.sort()
	count = 1
	total = 0
	for i in range(0, n - 1):
		if arr[i] == arr[i + 1]:
			count += 1
		else:
			total += (count - 1) * count / 2
			count = 1
	total += (count - 1) * count / 2
	return int(total)


def calculate(arr, n):
	k = 0
	for i in range(n):
		for j in range(i + 1, n):
			if i != j and arr[i] ^ arr[j] == 0:
				k += 1
	return k


def calculate(arr, n):
	dict1 = {}
	for i in arr:
		if i in dict1:
			dict1[i] += 1
		else:
			dict1[i] = 1
	count = 0
	for i in dict1.keys():
		if dict1[i] > 1:
			count += dict1[i] * (dict1[i] - 1) // 2
	return count


def calculate(arr, n):
	d = {}
	c = 0
	for i in arr:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for (i, j) in d.items():
		if d[i] >= 2:
			c += d[i] * (d[i] - 1) // 2
	return c


from math import factorial

def calculate(arr, n):
	arr.sort()
	i = 0
	sum = 0
	while i < n:
		k = arr.count(arr[i])
		if k >= 2:
			sum += factorial(k) / (factorial(k - 2) * factorial(2))
		i += arr.count(arr[i])
	return int(sum)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


def calculate(arr, n):
	count = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			if arr[i] ^ arr[j] == 0:
				count += 1
	return count
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


def calculate(arr, n):
	d = {}
	li = []
	arr.sort()
	for i in arr:
		d[i] = d.get(i, 0) + 1
	for i in d:
		li.append(d.get(i) * (d.get(i) - 1) // 2)
	return sum(li)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


def calculate(arr, n):
	a = dict()
	for i in arr:
		a[i] = a.get(i, 0) + 1
	v = 0
	for i in a.values():
		v += int(i * (i - 1) / 2)
	return v
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


def calculate(a, n):
	c = 0
	for i in range(n - 1):
		l = i + 1
		while l < n:
			if a[i] ^ a[l] == 0:
				c = c + 1
				l = l + 1
			else:
				l = l + 1
	return c
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


def calculate(a, n):
	a.sort()
	count = 1
	answer = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			count += 1
		else:
			answer = answer + count * (count - 1) // 2
			count = 1
	answer = answer + count * (count - 1) // 2
	return answer
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = calculate(arr, n)
	print(res)


from collections import Counter as C

def calculate(arr, n):
	z = []
	for (i, j) in C(arr).items():
		if j > 1:
			z.append(j)
	return sum(list(map(lambda x: x * (x - 1) // 2, z)))


def calculate(arr, n):
	arr.sort()
	count = 0
	res = 0
	i = 1
	while i < n:
		if arr[i] == arr[i - 1]:
			while i < n and arr[i] == arr[i - 1]:
				count += 1
				i += 1
			res += count * (count + 1) >> 1
			count = 0
		i += 1
	return res


from collections import Counter

def calculate(arr, n):
	ans = 0
	store = Counter(arr)
	xorArr = []
	for (k, v) in store.items():
		if v > 1:
			xorArr.append(v)
	for i in range(len(xorArr)):
		temp = xorArr[i] * (xorArr[i] - 1) // 2
		ans += temp
	return ans


def calculate(arr, n):
	map = {}
	for val in arr:
		if val in map:
			map[val] += 1
		else:
			map[val] = 1
	ans = 0
	for val in map.keys():
		freq = map[val]
		ans += freq * (freq - 1) // 2
	return ans


def calculate(arr, n):
	ans = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			xorsum = arr[j] ^ arr[i]
			if xorsum == 0:
				ans += 1
	return ans


def calculate(a, n):
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 0
	for i in d:
		if d[i] > 1:
			ans += d[i] * (d[i] - 1) // 2
	return ans


def calculate(arr, n):
	num_map = {}
	count = 0
	for num in arr:
		if num in num_map:
			num_map[num] += 1
		else:
			num_map[num] = 1
	for num in num_map:
		count += int(num_map[num] * (num_map[num] - 1) / 2)
	return count


def calculate(arr, n):
	mp = dict()
	ans = 0
	for i in range(len(arr)):
		curxor = 0 ^ arr[i]
		if curxor in mp.keys():
			ans += mp[curxor]
		if arr[i] in mp.keys():
			mp[arr[i]] += 1
		else:
			mp[arr[i]] = 1
	return ans