Given an array Arr of N integers.Calculate the sum of Bitwise ANDs(&) all the pairs formed by the given array.
Example 1:
Input:
N=3
Arr={5,10,15}
Output:
15
Explanation:
The bitwise Ands of all pairs are (5&10)=0
(5&15)=5 and (10&15)=10.Therefore,
total Sum=0+5+10=15.
Example 2:
Input:
N=4
Arr={10,20,30,40}
Output:
46
Explanation:
The sum of bitwise Ands 
of all pairs=0+10+8+20+0+8=46.
Your Task:
You don't need to read input or print anything.Your Task is to complete the function pairAndSum() which takes an Integer N and an array Arr as input parameters and returns the sum of bitwise Ands of all pairs.
Expected Time Complexity:O(N)
Expected Auxillary Space:O(1)
Constraints:
1<=N<=10^{5}
1<=Arr_{i}<=10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def pairAndSum(self,N,Arr):
        #code here

Solutions:
class Solution:

	def pairAndSum(self, N, Arr):
		c = [0] * 32
		for i in range(N):
			for j in range(32):
				if Arr[i] & 1 << j:
					c[j] += 1
		ans = 0
		for i in range(32):
			ans += c[i] * (c[i] - 1) // 2 * (1 << i)
		return ans


from collections import defaultdict as dd

class Solution:

	def pairAndSum(self, N, Arr):
		store = dd(lambda : 0)
		for item in Arr:
			num = bin(item)[2:]
			num = num[::-1]
			for (i, bitti) in enumerate(num):
				if bitti == '1':
					store[i] += 1
		summa = 0
		for item in store:
			summa += 2 ** item * store[item] * (store[item] - 1) // 2
		return summa


class Solution:

	def pairAndSum(self, N, Arr):
		matrix = []
		ans = 0
		for i in range(N):
			matrix.append([0] * 32)
		for i in range(32):
			count = 0
			mask = 1 << i
			for j in range(N):
				if Arr[j] & mask != 0:
					count += 1
			pairs = count * (count - 1) // 2
			ans = ans + pairs * (1 << i)
		return ans


class Solution:

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


class Solution:

	def pairAndSum(self, N, Arr):
		res = 0
		for i in range(32):
			temp = 0
			for j in range(N):
				if Arr[j] & 1 << i:
					temp += 1
			res += (1 << i) * (temp * (temp - 1) // 2)
		return res


class Solution:

	def pairAndSum(self, N, Arr):
		l = [0] * 32
		c = 0
		for i in Arr:
			s = bin(i)
			s = s[2:]
			s = (32 - len(s)) * '0' + s
			for j in range(31, -1, -1):
				if s[j] == '1':
					l[31 - j] += 1
		for i in range(32):
			c += l[i] * (l[i] - 1) // 2 * 2 ** i
		return c


import math

class Solution:

	def cust_fact(self, n):
		return int(n * (n - 1) / 2)

	def pairAndSum(self, N, Arr):
		total = 0
		for i in range(32):
			count = 0
			for x in range(N):
				if Arr[x] >> i & 1:
					count += 1
			if count < 2:
				continue
			combinations = self.cust_fact(count)
			total += combinations << i
		return total