Bit manipulation: Summation for all pairs in an array

Revision en1, by garg_saurav, 2020-12-27 18:18:25

Hi everyone, this is a question that was asked in a contest which is over now. Here is the problem statement:

Description
You are given an array A of length N. Consider that the array is one indexed.
You need to find the sum of (A[i] & A[j] & (A[i]+A[j])) for all pairs (i,j) such that 1<=i<j<=N.

Constraints
2<=N<=2x10^5
1<=A[i]<=10^9

Output Format
Since the answer can be large, return it modulo 10^9 + 7

I know the solution in the case when there is only (A[i] & A[j]). In this case, we can count the number of set bits at i'th position (= k). Then it will contribute to kC2 pairs in summation which can directly be written as kC2 x 2^i But I can't extend the argument to the above problem. Any links/references would be highly appreciated.

Tags bit manipulation, #problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English garg_saurav 2020-12-27 18:18:25 867 Initial revision (published)