How would you solve Bitwise and Sum from InterviewBit Bit Manipulation Contest

Problem Name : Bitwise and Sum

Description : You are given an Array A of length N. Consider that the array is one indexed.
You need to find sum of all (A[i] \land A[j] \land (A[i]+A[j])) for all pairs such that 1 \leq i < j \leq N. where \land represents bitwise and operation.

Problem Contrains:
1 \leq N \leq 2 \times 10^5
1\leq A[i] \leq 10^9

Input Format: The only argument contains the the integer array A.

Output Format: Return the sum of (A[i] \land A[j] \land (A[i]+A[j])) for all pairs. Since the answer can be large, return it modulo 10^9 + 7.

Example Input:
Input 1:
A : [8, 9]

Input 2:
A : [1, 3, 3]

Example Output:
Output 1:
0
Output 2:
2
Example Explaination:
Explaination 1:
There is only one pair - (8 & 9 & (8 + 9)) = 0
Explaination 2:
We have 3 pairs -
(1, 3) = 1 & 3 & (1+3) = 0
(1, 3) = 1 & 3 & (1+3) = 0
(3, 3) = 3 & 3 & (3+3) = 2

Contest Link : CodeDrift: Bit Manipulation - InterviewBit

4 Likes

@taran_1407 I saw you solved it fully. I was able to score partial marks in nbitbit.

Well my approach was as follows:
Consider any bit b (0-based), let’s find its contribution. Consider all elements of the array which have this bit set. A[i]\&A[j] == 1 for this bit b. We only need to find number of pairs such that A[i]+A[j] has b^{th} bit set in this number. Consider the numbers formed by last b bits of the numbers, for example if A[i] = 10 = (1010)_2 and b = 3, we get the number (010)_2 = 2. Now note that (A[i]+A[j]) has (b+1)^{th} bit set(since A[i] and A[j] had b^{th} bit set). Also b{th} bit should be set. Therefore the condition comes out to be: A[i] + A[j] - 2^{b+1} - 2^{b} \ge 0. This means A[j] \geq 3*2^b - A[i]. So iterate on position i and find j using binary search. My code:

Code
int Solution::solve(vector<int> &A) {
    long long ans = 0;
    int n = A.size();
    int i, j;
    int bit;
    for(bit = 0; bit < 30; bit++)
    {
        vector<long long> vec;
        for(i = 0; i < n; i++)
            if((A[i] >> bit)&1)
            {
                long long x = (A[i] >> (bit+1));
                x = x*(1 << (bit+1));
                vec.push_back(A[i] - x);
            }
        sort(vec.begin(), vec.end());
        for(i=0;i<vec.size(); i++)
        {
            int val = (1 << (bit+1)) + (1 << bit) - vec[i];
            int idx = lower_bound(vec.begin()+i+1, vec.end(), val) - vec.begin();
            ans+=(vec.size()-idx)*1ll*(1 << bit);
        }
            
    }
    ans = ans%(1000000000+7);
    return ans;
}
5 Likes

thanks this was helpful.

Hi
My approach was the same as @samarth2017, Although when adding elements with b-th bit on to a separate list, I took values modulo 2^{bit}, so that way I sorted and used pointer approach to count the number of pairs with the sum at least 2^{bit}. Its complexity is O(N*log(N)*log(max(A_i))).

3 Likes

do you know if their compilers support policy based data structures or not ? i was submitting the solution using pbds ordered set but my function returned 0 and the output in other compilers is right … i dont know why my ouput is wrong in this

I don’t think you can include extra libraries. You have to complete the function only.

1 Like

ok :slight_smile: thanks…

can you please help provide solutions and explanations to questions 1, 2, and 3?

Tell me your approach/ideas because Q2 and Q3 were straightforward. Maybe I can optimize your ideas?