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
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;
}
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))).
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
thanks…