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

**URL:** <https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912>\
**Category:** Uncategorized\
**Created:** [December 27, 2020, 7:18pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912 "2020-12-27T19:18:05Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![sedlif](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sedlif/32/24644_2.png) [@sedlif](https://discuss.codechef.com/u/sedlif)\
**Post date:** [December 27, 2020, 7:18pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/1 "2020-12-27T19:18:05Z")

</div>

**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](https://www.interviewbit.com/contest/code-drift-bit-manipulation/)

---

<div class="post-metadata">

**Author:** ![subham301477](https://discuss.codechef.com/user_avatar/discuss.codechef.com/subham301477/32/24644_2.png) [@subham301477](https://discuss.codechef.com/u/subham301477)\
**Post date:** [December 28, 2020, 3:31am UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/2 "2020-12-28T03:31:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![samarth2017](https://discuss.codechef.com/user_avatar/discuss.codechef.com/samarth2017/32/274045_2.png) [@samarth2017](https://discuss.codechef.com/u/samarth2017)\
**Post date:** [December 28, 2020, 7:25am UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/3 "2020-12-28T07:25:48Z")

</div>

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**
>
> ```auto
> 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;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![sedlif](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sedlif/32/24644_2.png) [@sedlif](https://discuss.codechef.com/u/sedlif)\
**Post date:** [December 28, 2020, 9:45am UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/4 "2020-12-28T09:45:35Z")

</div>

thanks this was helpful.

---

<div class="post-metadata">

**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\
**Post date:** [December 28, 2020, 11:02pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/5 "2020-12-28T23:02:05Z")

</div>

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))).

---

<div class="post-metadata">

**Author:** ![spyder101](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spyder101/32/151185_2.png) [@spyder101](https://discuss.codechef.com/u/spyder101)\
**Post date:** [December 31, 2020, 1:07pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/6 "2020-12-31T13:07:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![samarth2017](https://discuss.codechef.com/user_avatar/discuss.codechef.com/samarth2017/32/274045_2.png) [@samarth2017](https://discuss.codechef.com/u/samarth2017)\
**Post date:** [December 31, 2020, 1:40pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/7 "2020-12-31T13:40:49Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![spyder101](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spyder101/32/151185_2.png) [@spyder101](https://discuss.codechef.com/u/spyder101)\
**Post date:** [December 31, 2020, 1:47pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/8 "2020-12-31T13:47:10Z")

</div>

ok 🙂 thanks…

---

<div class="post-metadata">

**Author:** ![ganesh\_g76](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ganesh_g76/32/30182_2.png) [@ganesh\_g76](https://discuss.codechef.com/u/ganesh_g76)\
**Post date:** [January 3, 2021, 1:25pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/9 "2021-01-03T13:25:34Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![samarth2017](https://discuss.codechef.com/user_avatar/discuss.codechef.com/samarth2017/32/274045_2.png) [@samarth2017](https://discuss.codechef.com/u/samarth2017)\
**Post date:** [January 3, 2021, 4:39pm UTC](https://discuss.codechef.com/t/how-would-you-solve-bitwise-and-sum-from-interviewbit-bit-manipulation-contest/82912/10 "2021-01-03T16:39:32Z")

</div>

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