This content originally appeared on DEV Community and was authored by Abhinandan Sharma
Introduction
If you have come to this post, I bet you are struggling with all those bit operations and tricks as there are two many of them! These bit operations are not only useful in competitive programming questions but also in Dynamic Programming (where we have to save the current state), and reducing time complexities in certain scenarios.
Before heading to discuss the questions let's just get a glimpse of why you should learn bitsets and type of questions which you can't do if you don't have enough knowledge of bit manipulation.
Maximum AND/OR/XOR value of a pair in an array
Queries for bitwise AND in the index range [L, R] of the given array.
Find Longest substring containing vowels in even counts, Find Longest awesome substring, Number of wonderful sub-strings, Maximum Product of Word Lengths These type of questions are typically solved using bitsets easily.
We will be discussing each of the above questions and in the end, I would be sharing some of the questions from codeforces, Leetcode, etc. If you have any doubts in those questions, feel free to discuss in the comments.
First Type of Questions
Questions asking you to compute the maximum AND/XOR/OR of any pair in an array, directly or indirectly, are actually based on a rather simple trick. Let's First discuss the questions.
Q1. Find Maximum Binary AND pair from an array.
Codeforces Link of the problem:
Input: arr=[2,6,4,5,12,14,15]
Output: Max And pair: 14
This is rather a difficult problem to solve but this will let you think much.
Hint 1: First convert all the numbers to their binary forms and see if you see a pattern in finding the answer
Hint 2: The size of the numbers can be at most 32 bits.
Solution: Read Hint 2 one more time. We know that total digits in binary representation can't be more than 32 for int datatype. Now, think this way: We have to see if a bit can be set or unset in our answer. That means we are actually constructing our answer bit by bit.
We would do a simple iteration here starting from leftmost bit and then we would search for the elements in array having this bit as set (And also the all the bits in our current answer). If the number of such elements is greater than or equal to 2, we would add this bit in our answer.
Dry Run:
arr[]={2,6,4,5,12,14,15}
Binary form of these numbers:
0010
0110
0100
0101
1100
1110
1111
Now Our max answer can't be more than the maximum of these numbers(It's binary AND). So our max answer can be 15. We would start by setting the leftmost bit.
Initial Answer : 0000
First bit set: 1000 which is 8 in decimal. Fourth bit set in 12,
15 and 14. (Greater than 2) So, we add this bit to our answer
Second Bit: 1100 which is 12 in decimal. The number of elements
in which both first and second bit is set is 3(12,14 and 15). So,
we add this bit.
Third Bit: 1110 which is 14 in decimal. The number of elements in
which all of the set bits of 14 are present is 2(14 and 15). So,
we add this bit as well.
Fouth bit: 1111 which is 15 in decimal. the number of elements in
which all of the set bits of 15 are present is 1 only(15
itself). So, we would not add this bit and reset our answer to
1110.
Why does this work?
A very frequent doubt which comes in mind is, how this algorithm differentiates between two numbers added in the answer. Like, I am first considering 12, 14 in for the second bit but there can be some number which actually satisfies our conditions but 12 don't. So the set bits of 12 would be removed! This would cause "some error". First of all, see the conditions clearly, the condition to add a number is that it should have bits added so far, so 12 won't be contributing any unique bit...
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
bool isValid(int x, vector<int> &arr, int n)
{
int cnt = 0;
for(int i = 0; i < n; i++)
{
// How do I check if all bits set in answer is set in the element as well?
// Just do an AND operation!
if((x & arr[i]) == x)
cnt++;
}
return cnt >= 2;
}
int findMaxAndPair(vector<int> &arr, int n)
{
int ans = 0;
// Here I am starting from 63 as it is long long
// You can actually compute the maximum number
// and start from it's rightmost set bit
for(int i = 31; i >= 0; i--)
{
// How do I set a specific bit? Just do an OR operation on shifted bit!
if(isValid(ans | (1 << i), arr, n))
{
ans = ans | (1 << i);
}
}
return ans;
}
int32_t main()
{
int n;
cin >> n;
vector<int> arr (n);
for(int i = 0; i < n; i++)
cin >> arr[i];
cout << findMaxAndPair(arr, n);
return 0;
}
Second Type
Querying inside a specific range. To be continued...
This content originally appeared on DEV Community and was authored by Abhinandan Sharma
Abhinandan Sharma | Sciencx (2021-08-06T10:15:20+00:00) Bitsets, Bit Manipulations and Bitmasks Questions. Retrieved from https://www.scien.cx/2021/08/06/bitsets-bit-manipulations-and-bitmasks-questions/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.