Problem Link - Bit Manipulation - Sum of Bits
Problem Statement
You are given an array A_1, A_2, \dots, A_N of length N.
We define f(i, j) = number of corresponding bits in binary representation of A_i and A_j which are different. For example, the array A=[6, 10, 15] then f(2, 3) = 2 since binary representation of A_2 and A_3 are 1010 and 1111. The second and the fourth bit differ, so f(2, 3) = 2.
Find the value of \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j).
Approach:
The code idea is to count the differing bits between all pairs without directly comparing each pair, which would be inefficient. Instead, we examine each bit position from 0 to 30 (assuming 31-bit integer representation) and calculate how many numbers in the array have a 1 at each bit position. This count is stored as co. For each bit position, the number of pairs that have differing bits at that position can be determined by multiplying co (the count of numbers with the bit set) by (n−co) (the count of numbers with the bit unset). This product represents the total differing bits for that bit position across all pairs. We then add this product to our result. By repeating this process for each bit position, we get the total number of differing bits across all pairs in the array.
Time Complexity:
O(N) for iterating through the array across 31 bit positions.
Space Complexity:
O(1) for a constant amount of extra space.