Given an integer array of N integers, find sum of bit differences in all pairs that can be formed from array elements. Bit difference of a pair (x, y) is count of different bits at same positions in binary representations of x and y.
For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 (first and last bits differ in two numbers).
Note: (x, y) and (y, x) are considered two separate pairs.
Example 1:
Input: 
N = 2
arr[] = {1, 2}
Output: 4
Explanation: All pairs in array are (1, 1)
(1, 2), 2, 1), (2, 2)
Sum of bit differences = 0 + 2 + 2 + 0
                       = 4
Example 2:
Input:
N = 3 
arr[] = {1, 3, 5}
Output: 8
Explanation: 
All pairs in array are (1, 1), (1, 3),
(1, 5), (3, 1), (3, 3) (3, 5),(5, 1),
(5, 3), (5, 5)
Sum of bit differences =  0 + 1 + 1 +
                          1 + 0 + 2 +
                          1 + 2 + 0 
                       = 8
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sumBitDifferences() which takes the array arr[] and n as inputs and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3
class Solution:

	
	def sumBitDifferences(self,arr, n):
    	# code here


Solutions:
class Solution:

	def sumBitDifferences(self, arr, n):
		n = len(arr)
		sum_bit_diff = 0
		for i in range(32):
			count_set_bits = 0
			count_clear_bits = 0
			for j in range(n):
				if arr[j] & 1 << i:
					count_set_bits += 1
				else:
					count_clear_bits += 1
			sum_bit_diff += count_set_bits * count_clear_bits * 2
		return sum_bit_diff


class Solution:

	def sumBitDifferences(self, arr, N):
		result = 0
		for i in range(32):
			countSet = 0
			countUnset = 0
			for j in range(N):
				if arr[j] & 1 << i:
					countSet += 1
				else:
					countUnset += 1
			result += countSet * countUnset * 2
		return result


class Solution:

	def sumBitDifferences(self, A, N):
		cnt = 0
		maxi = max(A)
		z = len(bin(maxi)[2:])
		li = [bin(x)[2:].zfill(z) for x in A]
		l = [0 for i in range(z)]
		for x in li:
			i = 0
			for ch in x:
				if ch == '0':
					l[i] += 1
				i += 1
		for x in l:
			cnt += 2 * x * (N - x)
		return cnt


class Solution:

	def sumBitDifferences(self, arr, n):
		res = 0
		for i in range(32):
			count1s = 0
			for x in arr:
				if x & 1 << i != 0:
					count1s += 1
			count0s = len(arr) - count1s
			bitDiff = count1s * 2 * count0s
			res += bitDiff
		return res


class Solution:

	def sumBitDifferences(self, arr, n):
		ans = 0
		for j in range(32):
			cnt = 0
			for i in arr:
				if i >> j & 1 == 1:
					cnt += 1
			ans += 2 * cnt * (len(arr) - cnt)
		return ans


class Solution:

	def sumBitDifferences(self, arr, n):
		res = 0
		for i in range(32):
			count = 0
			for j in range(n):
				if arr[j] & 1 << i:
					count += 1
			res += count * (n - count) * 2
		return res


class Solution:

	def sumBitDifferences(self, arr, n):
		l = len(arr)
		mx = max(arr)
		bitlen = mx.bit_length()
		k = 0
		for i in range(bitlen):
			c = 0
			for j in arr:
				if j >> i & 1:
					c += 1
			k += 2 * c * (l - c)
		return k


class Solution:

	def sumBitDifferences(self, arr, n):
		o = 0
		r = 0
		for i in range(32):
			o = 0
			for j in arr:
				if j >> i & 1 == 1:
					o += 1
			r += 2 * o * (len(arr) - o)
		return r


class Solution:

	def sumBitDifferences(self, arr, n):
		a = 0
		for j in range(32):
			c = 0
			for i in arr:
				if i >> j & 1 == 1:
					c += 1
			a += 2 * c * (len(arr) - c)
		return a


class Solution:

	def sumBitDifferences(self, arr, n):
		c = 0
		for j in range(max(arr).bit_length()):
			c1 = 0
			for i in arr:
				if i >> j & 1 == 1:
					c1 += 1
			c += 2 * c1 * (n - c1)
		return c


class Solution:

	def sumBitDifferences(self, arr, n):
		arr = list(arr)
		m = r = 0
		for i in range(max(arr).bit_length()):
			m = 0
			for j in arr:
				if j >> i & 1 == 1:
					m += 1
			r += 2 * m * (len(arr) - m)
		return r


class Solution:

	def sumBitDifferences(self, arr, n):
		ans = 0
		for i in range(32):
			(c1, c2) = (0, 0)
			for j in range(n):
				if arr[j] & 1 << i > 0:
					c1 += 1
				else:
					c2 += 1
			ans += c1 * c2
		return ans * 2


from itertools import permutations

class Solution:

	def sumBitDifferences(self, arr, n):
		ans = 0
		for j in range(32):
			cnt = 0
			for i in arr:
				if i >> j & 1 == 1:
					cnt += 1
			ans += 2 * cnt * (len(arr) - cnt)
		return ans


class Solution:

	def sumBitDifferences(self, arr, n):
		main_count = 0
		c = 0
		zero = 0
		count = 0
		for k in range(32):
			count = 0
			for i in range(n):
				if arr[i] >> k & 1 == 1:
					count += 1
			zero = n - count
			main_count += zero * count
		return main_count * 2


from itertools import combinations

class Solution:

	def sumBitDifferences(self, arr, n):
		c = 0
		for i in range(32):
			d = 0
			for j in arr:
				if j >> i & 1 == 1:
					d += 1
			c += 2 * d * (n - d)
		return c


class Solution:

	def sumBitDifferences(self, arr, n):
		res = 0
		k = max(arr)
		for i in range(0, k.bit_length()):
			cnt = 0
			for j in arr:
				if j >> i & 1 == 0:
					cnt += 1
			res += 2 * cnt * (n - cnt)
		return res


class Solution:

	def sumBitDifferences(self, arr, n):
		sum = 0
		v = max(arr)
		for i in range(v.bit_length()):
			setbits = 0
			for j in arr:
				if j >> i & 1:
					setbits += 1
			sum += 2 * setbits * (n - setbits)
		return sum


class Solution:

	def sumBitDifferences(self, arr, n):
		sum = 0
		for i in range(32):
			setbits = 0
			for j in arr:
				k = j >> i
				if k & 1:
					setbits += 1
			sum += 2 * setbits * (n - setbits)
		return sum


import math

class Solution:

	def sumBitDifferences(self, arr, n):
		m = int(math.log2(max(arr))) + 1
		ans = 0
		for i in range(m):
			cnt = 0
			for j in arr:
				if j >> i & 1:
					cnt += 1
			ans += 2 * cnt * (n - cnt)
		return ans


class Solution:

	def sumBitDifferences(self, arr, n):
		res = [0] * 32
		for i in arr:
			k = 0
			while i:
				if i & 1:
					res[k] += 1
				k += 1
				i >>= 1
		s = 0
		n = len(arr)
		for i in res:
			if i:
				s += (n - i) * i * 2
		return s


class Solution:

	def sumBitDifferences(self, arr, n):
		d = []
		ans = 0
		for i in range(0, 31):
			c = 0
			for j in arr:
				if j & 1 << i:
					c += 1
			d.append(c)
		for i in d:
			ans += 2 * (i * (n - i))
		return ans


def diff(a, b):
	x = a ^ b
	c = 0
	while x:
		c += 1
		x = x & x - 1
	return c

class Solution:

	def sumBitDifferences(self, arr, n):
		m = len(bin(max(arr))) - 2
		l0 = [0] * m
		l1 = [0] * m
		for x in arr:
			for i in range(m):
				if x & 1:
					l1[i] += 1
				else:
					l0[i] += 1
				x >>= 1
		c = 0
		for x in range(m):
			c += l0[x] * l1[x]
		return c << 1


class Solution:

	def sumBitDifferences(self, arr, n):
		ans = 0
		for i in range(32):
			(zero, one) = (0, 0)
			for num in arr:
				if num & 1 << i:
					one += 1
				else:
					zero += 1
			ans += one * zero
		return 2 * ans


NOOFBITS = 17

class Solution:

	def sumBitDifferences(self, arr, siz):
		bitsum = [0] * NOOFBITS
		for n in arr:
			j = 0
			while n > 0:
				bitsum[j] += n & 1
				n >>= 1
				j += 1
		total = 0
		for noofones in bitsum:
			noofzeroes = siz - noofones
			total += noofones * noofzeroes * 2
		return total