Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the

Sum of XOR of all pairs of the array OR 
Sum of XOR of all subsets  

Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.


 Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.

 Input                                               Output

 3                                                       28
 1 5 6

 Explanation:

 The most important clue for solving these questions is to find a pattern with respect to the                property of XOR. 

1 =     001
5 =     101
6 =     110
1 ^ 5 = 100
1 ^ 6 = 111
5 ^ 6 = 011
1^5^6 = 010
Total number of subsets possible is 2n  And we can see each bit from 0 to 2 contributes 1 exactly (2n)/2 times. So If there is any value of array that has set tth bit set, then exactly half of 2n subsets will contribute to 2n-1+i to the final sum.

 Solution:

 
#include<bits/stdc++.h>
using namespace std;

int xorSum(int arr[], int n)
{
 int bits = 0;
 for (int i=0; i < n; ++i)
  bits |= arr[i];
 int ans = bits * pow(2, n-1);
 return ans;
}

int main()
{
 int n;
 cin>>n;
 int a[n];
 for(int i=0;i<n;i++){
  cin>>a[i];
 cout<<xorSum(a,n);
}


 Question 2: SUM_XOR_PAIRS_ARRAY

 Input                                  Output
 
 3                                         12
 7 3 5
 
  Explanation:

 When looking at the nth bit (where the rightmost bit is the 0th), count how many numbers have 0 (call this an) and how many have 1 (call this bn). The contribution towards the final sum will be  an*bn*2n. You need to do this for each bit and sum all these contributions together.

Solution:

#include <iostream>
using namespace std;

int main() {
    long long int n,i,j,k;

    cin>>n; 
 
    long long int arr[n],ans=0;

    for(i=0;i<n;i++)
        cin>>a[i];

    for(i=0;i<32;i++)
    {
        k=0; 
        for(j=0;j<n;j++)
            if((arr[j] & (1<<i)))
                k++;

        ans+= (1<<i)*(k*(n-k));     
    }
    cout<<ans<<endl;
    return 0;
}

Question 3: 

Given an array A[] of size N. Now you are given Q queries to be performed over this array. In each query, you are given 2 space separated integers L and R. For each query, you need to you need to find the summation of the xor-sum of all triplets (i,j,k) of the sub-array L...R , where L≤i<j<k≤R.
In short, you need to find ∑(A[i]⊕A[j]⊕A[k]), over all triplets (i,j,k) , such that L≤i<j<k≤R . Print the answer for each query , Modulo 109+7

This was a question of a hiring contest. Try solving it. Quite similar to the previous problem.


Practice Problems:
















Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below cod...
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions ...
Read more