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.
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$$$.
Thanks @Trgt_2021_explosion
hey bro i know its 2 years but in your solution you do not maintain the condition that 1<=i<j<=n, You just sort which change whole order . I dont know how your code gets acepted ??
if a contest is over why dont you give a link?
Sure. Here you go!