Given an array of N integers, find the sum of xor of all pairs of numbers in the array.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {7, 3, 5}
Output : 12
Explanation:
All possible pairs and there Xor
Value: ( 3 ^ 5 = 6 ) + (7 ^ 3 = 4)
 + ( 7 ^ 5 = 2 ) =  6 + 4 + 2 = 12
Ã¢â¬â¹Example 2:
Input : arr[ ] = {5, 9, 7, 6} 
Output :  47
 
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 sumXOR() that takes an array (arr), sizeOfArray (n), and returns the sum of xor of all pairs of numbers in the array. The driver code takes care of the printing.
Expected Time Complexity: O(N Log N).
Expected Auxiliary Space: O(1).
Constraints
2 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:
    def sumXOR (self, arr, n) : 
        #Complete the function
    


Solutions:
class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		for i in range(32):
			freq = 0
			for j in range(n):
				if arr[j] & 1 << i:
					freq += 1
			ans += freq * (n - freq) * (1 << i)
		return ans


import math

class Solution:

	def sumXOR(self, nums, n):
		ans = 0
		for i in range(1 + int(math.log(max(nums), 2))):
			(set, unset) = (0, 0)
			for j in range(n):
				if nums[j] >> i & 1:
					set += 1
				else:
					unset += 1
			ans = ans + set * unset * 2 ** i
		return ans


class Solution:

	def sumXOR(self, nums, n):
		ans = 0
		for i in range(32):
			(set, unset) = (0, 0)
			for j in range(n):
				if nums[j] >> i & 1:
					set += 1
				else:
					unset += 1
			ans = ans + set * unset * 2 ** i
		return ans


class Solution:

	def sumXOR(self, arr, n):
		sum = 0
		for i in range(0, 32):
			zc = oc = 0
			for j in range(n):
				if arr[j] % 2 == 0:
					zc += 1
				else:
					oc += 1
				arr[j] = arr[j] >> 1
			sum += oc * zc * (1 << i)
		return sum


class Solution:

	def sumXOR(self, arr, n):
		s = 0
		for i in range(32):
			c0 = 0
			c1 = 0
			for j in arr:
				if j & 1 << i:
					c1 += 1
				else:
					c0 += 1
			s += c0 * c1 * (1 << i)
		return s


import math

class Solution:

	def sumXOR(self, arr, n):

		def checkbit(i, j):
			if i >> j & 1:
				return True
			else:
				return False
		ans = 0
		for i in range(30):
			(c1, c0) = (0, 0)
			for j in range(n):
				if checkbit(arr[j], i):
					c1 += 1
				else:
					c0 += 1
			ans = ans + c1 * c0 * (1 << i)
		return ans


class Solution:

	def sumXOR(self, arr, n):
		su = 0
		for i in range(32):
			num_set = 0
			num_unset = 0
			for num in arr:
				if num >> i & 1:
					num_set += 1
				else:
					num_unset += 1
			if num_set * num_unset > 0:
				su = su + num_set * num_unset * (1 << i)
		return su


class Solution:

	def sumXOR(self, arr, n):
		result = 0
		for i in range(20):
			mask = 2 ** i
			cnt = 0
			for e in arr:
				if e & mask == mask:
					cnt += 1
			result += cnt * (n - cnt) * mask
		return result


class Solution:

	def sumXOR(self, arr, n):
		res = 0
		for i in range(32):
			(cnt0, cnt1) = (0, 0)
			for j in arr:
				if j & 1 << i:
					cnt1 += 1
				else:
					cnt0 += 1
			res += 2 ** i * (cnt0 * cnt1)
		return res


class Solution:

	def sumXOR(self, arr, n):
		sm = 0
		for i in range(32):
			count_1 = 0
			count_0 = 0
			for j in range(n):
				if arr[j] % 2 == 0:
					count_0 += 1
				else:
					count_1 += 1
				arr[j] = arr[j] // 2
			sm += count_1 * count_0 * (1 << i)
		return sm


class Solution:

	def sumXOR(self, arr, n):
		totalXorVal = 0
		for i in range(31):
			zeroBitsCount = 0
			oneBitsCount = 0
			for num in arr:
				if num & 1 << i == 0:
					zeroBitsCount += 1
				else:
					oneBitsCount += 1
			possiblePairings = zeroBitsCount * oneBitsCount
			totalXorVal += (1 << i) * possiblePairings
		return totalXorVal


class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		for i in range(31):
			count = 0
			for num in arr:
				if num >> i & 1 == 1:
					count += 1
			ans += count * (n - count) * 2 ** i
		return ans


class Solution:

	def sumXOR(self, arr, n):
		l = [0] * 32
		for i in arr:
			s = bin(i)
			s = s[2:]
			c = 0
			for j in s[::-1]:
				if j == '1':
					l[c] += 1
				c += 1
		p = 1
		s = 0
		for i in l:
			s += i * (n - i) * p
			p = p * 2
		return s


class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		temp = [0 for i in range(18)]
		for i in range(18):
			if arr[0] & 1 << i:
				temp[i] += 1
		for k in range(1, n):
			for i in range(18):
				bit = arr[k] & 1 << i
				if bit == 0:
					ans += (1 << i) * temp[i]
				else:
					ans += (1 << i) * (k - temp[i])
					temp[i] += 1
		return ans


class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		for i in range(32):
			x = 0
			y = 0
			bit = 1 << i
			for j in arr:
				set = bit & j
				if set:
					x += 1
				else:
					y += 1
			ans += x * y * bit
		return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.sumXOR(arr, n)
	print(res)


class Solution:

	def sumXOR(self, arr, n):
		sum = 0
		i = 0
		while i < 32:
			zc = oc = 0
			for ele in arr:
				if ele & 1 << i:
					oc += 1
				else:
					zc += 1
			sum += zc * oc * (1 << i)
			i += 1
		return sum
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.sumXOR(arr, n)
	print(res)


class Solution:

	def sumXOR(self, arr, n):
		s = 0
		for i in range(32):
			(e, o) = (0, 0)
			for j in range(n):
				if arr[j] & 1:
					o += 1
				else:
					e += 1
				arr[j] //= 2
			s += e * o * 2 ** i
		return s


class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		bits = [0] * 33
		for i in range(33):
			for j in arr:
				bits[i] += 1 << i & j != 0
		s = sum(bits)
		ans = 0
		for i in range(33):
			ans += (1 << i) * bits[i] * (n - bits[i])
		return ans


class Solution:

	def sumXOR(self, arr, n):
		cur = 0
		large = max(arr)
		ans = 0
		while 1 << cur <= large:
			zero = 0
			one = 0
			for i in range(n):
				if arr[i] & 1 << cur > 0:
					one += 1
				else:
					zero += 1
			ans += (1 << cur) * zero * one
			cur += 1
		return ans


import math

class Solution:

	def sumXOR(self, arr, n):
		ans = 0
		k = int(math.log2(max(arr))) + 1
		for i in range(k):
			zc = 0
			oc = 0
			idsum = 0
			for j in range(0, n):
				if arr[j] % 2 == 0:
					zc += 1
				else:
					oc += 1
				arr[j] = int(arr[j] / 2)
			idsum = oc * zc * (1 << i)
			ans += idsum
		return ans


class Solution:

	def isset(self, a, n):
		return a & 1 << n != 0

	def sumXOR(self, a, n):
		o = [0] * 17
		z = [0] * 17
		for i in a:
			for j in range(17):
				if self.isset(i, j):
					o[j] += 1
				else:
					z[j] += 1
		x = 1
		ans = 0
		for i in range(17):
			y = o[i] * z[i]
			ans += y * x
			x <<= 1
		return ans