garg_saurav's blog

Bit manipulation: Summation for all pairs in an array
By garg_saurav, history, 4 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

The idea is we will compute bit by bit contribution. For $$$i^{th}$$$ bit let $$$A=a_{i_1},a_{i_2},...,a_{i_k}$$$ be the sequence of number from the array whose $$$i^{th}$$$ bit is set. Let $$$X=2^i-1$$$. Now in this sequence for any two elements $$$(A[i]+A[j])$$$ has $$$i^{th}$$$ bit set $$$iff$$$ $$$XandA[i]+XandA[j]\,>=2^i$$$. This can be efficiently computed using two pointer method if A is sorted after anding with $$$X$$$.

My accepted Java Code
→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

if a contest is over why dont you give a link?

→ Reply