Problem: 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).
For example:
Method 2: An Efficient Solution can solve this problem in O(n) time using the fact that all numbers are represented using 32 bits (or some fixed number of bits). The idea is to count differences at individual bit positions. We traverse from 0 to 31 and count numbers with i’th bit set. Let this count be ‘count’. There would be “n-count” numbers with i’th bit not set. So count of differences at i’th bit would be count * (n-count) * 2.
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).
For example:
Input: arr[] = {1, 3, 5}
Output: 8
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
Method 1: A Simple Solution is to run two loops to consider all pairs one by one. For every pair, count bit differences. Finally return sum of counts.
int sumBitDifferences(int arr[], int n)
{
/* initialize result */
int ans = 0;
/* selecting pair of numbers using 2 loops */
for(int i = 0; i < arr.size(); i++)
{
for(int j = 0; j < arr.size(); j++)
{
/* diff is zero for pair with same numbers,
hence ignore */
if(arr[i] != arr[j])
{
/* xor gives the diff between two numbers */
int xor = arr[i] ^ arr[j];
/* setbits for the diff between two numbers */
while(xor > 0)
{
xor &= xor - 1;
ans++;
}
}
}
}
return ans;
}
Time complexity: O(n2).
Method 2: An Efficient Solution can solve this problem in O(n) time using the fact that all numbers are represented using 32 bits (or some fixed number of bits). The idea is to count differences at individual bit positions. We traverse from 0 to 31 and count numbers with i’th bit set. Let this count be ‘count’. There would be “n-count” numbers with i’th bit not set. So count of differences at i’th bit would be count * (n-count) * 2.
int sumBitDifferences(int arr[], int n)
{
/* initialize result */
int ans = 0;
/* traverse over all bits */
for (int i = 0; i < 32; i++)
{
/* count number of elements with i'th bit set */
int count = 0;
for(int j = 0; j < n; j++)
{
if( (arr[j] & (1 << i)) )
count++;
}
/* Add "count * (n - count) * 2" to the answer */
ans += (count * (n - count) * 2);
}
return ans;
}
Time complexity: O(n).