CODEWITHSUNDEEP
arraysalgorithmbit-manipulation
loremIpsum1771
loremIpsum1771

Reputation: 2527

Sum of bit differences among all pairs

The problem statement is the following:

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).

Examples:

Input: arr[] = {1, 2}
Output: 4
All pairs in array are (1, 1), (1, 2)
                       (2, 1), (2, 2)
Sum of bit differences = 0 + 2 +
                         2 + 0
                      = 4

Based on this post the most efficient (running time of O(n)) solution is the following:

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″. 

// C++ program to compute sum of pairwise bit differences
#include <bits/stdc++.h>
using namespace std;

int sumBitDifferences(int arr[], int n)
{
    int ans = 0;  // Initialize result

    // 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;
}

// Driver prorgram
int main()
{
    int arr[] = {1, 3, 5};
    int n = sizeof arr / sizeof arr[0];
    cout << sumBitDifferences(arr, n) << endl;
    return 0;
}

What I'm not entirely clear on is how the running time would be linear when there are two for loops incrementing by 1 for each iteration. The way I'm interpreting it is that since the outer loop is iterating from 0 to 32 (corresponding to the 0th and 32nd bits of each number) and because I'm guessing all 32 bit shifts would happen in the same clock period (or relatively fast compared to linear iteration), the overall running time would be dominated by the linear iteration over the array.

Is this the correct interpretation?

Upvotes: 0

Views: 4397

Answers (2)

alGOds
alGOds

Reputation: 159

Instead of comparing two numbers we could compare the i_th bit of every number with each other which would reduce your time complexity from O(n*n) to O(32*n), We just need to count the total pairs of zeroes and ones possible wrt i_th bit of every number. Simple Cpp implementation would look like this:

int cntBits(vector<int> &A) {
    int n = A.size();
    int ans = 0;
    for(int i=0;i<31;i++) {
        long long z = 0,o = 0;
        for(int j=0;j<n;j++) {
            if( ((A[j]>>i)&1 ) == 1 ) o++;
            else z++;
        }
        ans  = ( ans + (z*o)%1000000007 )%1000000007;
    }
    return (2*ans)%1000000007;
}

Anyone who is feeling stuck over this logic can refer to this explanation: https://www.youtube.com/watch?v=OKROwC2fLEg

Upvotes: 0

Trevor Merrifield
Trevor Merrifield

Reputation: 4691

In English, "My algorithm runs in O(n) time" translates to "My algorithm runs in time that is at most proportional to n for very large inputs". The proportionality aspect of that is the reason that 32 iterations in an outer loop don't make any difference. The execution time is still proportional to n.

Let's look at a different example:

for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        // do something
    }
}

In this example the execution time is proportional to n2 so it's not O(n). It is however O(n2). And technically O(n3) and O(n4), ... as well. This follows from the definition.

There's only so much you can talk about this stuff in English without misinterpretation, so if you want to nail down the concepts you're best off checking out the formal definition in an introductory algorithms textbook or online class and working out a few examples.

Upvotes: 4

Related Questions