Hello ,
lets start from a basic question that can be solved using Binary number's Knowledge.
LeetCode Poor Pig
Basically in above question you are given n number of poison bottle, and t number of trial you can do ,how many minimum pig you need to find the bottle with poison.
Solution using Binary number knowledgelet say number Bottle is 2 and one trial then how many pig we need ?
1 because we are going to feed first bottle to pig 1 if dies then there there is poison in bottle 1 otherwise there is poison in bottle 2.
We can generalize above idea for in binary number.How?
Lets name all bottle from 1 to N .
if in poison bottle I want to know whether in its binary representation first digit is 0 or 1 to do that I will feed pig 1 all bottle in which first digit is one (like 1,3,5,..) if Pig 1 dies then first digit (in binary representation ) is one otherwise 0.
similairy process can be done for other digits
If we have more number of trial than 1 then (lets say 2) we instead of binary number number we can use ternary number.
so this way we will get answer as ceil(log(t+1)(n)); log base t+1 (n)
Trick 1
We can Hash any string to bit mask .
Lets start with simple example :-
Count number of different char in string
Using setWe can use set or bool array to count character
int count(string & s) {
set<char>st;
for (char i : s) {
st.insert(i);
}
return st.size();
}
Using BitMaskint count(string & s) {
int mask = 0;
for (char i : s) {
mask |= (1 << (i - 'a'));
}
return __builtin_popcount(mask);
}
We can use this trick to reduce the constant factor of 26 in many different kind of problem.
lets take a example
Leetcode Maximum Product of Word Lengths
If you will try to solve this question using boolean array the time complexity will be O(n*n*26) that will lead to tle but you can improve time complexty to O(n*n) just by using bitmask
Soution Using BitMaskclass Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> a(words.size() , 0);
for(int i = 0;i < words.size();i++){
for(int j = 0;j < words[i].size();j++){
a[i] |= 1 << (words[i][j] - 'a');
}
}
int res = 0;
for(int i = 0;i < words.size();i++){
for(int j = i + 1;j < words.size();j++){
if((a[i] & a[j]) == 0){
if(words[i].size() * words[j].size() > res){
res = words[i].size() * words[j].size();
}
}
}
}
return res;
}
};
Trick 2
Printing all subset of K
What do I mean by subset
let say we have number whose binary representation is 1011 then we keep 0 as it is and we can make 1 to 0 or can keep 1.
Subsets of 1011 are 0011 , 1010 , 1011 and so on . 1100 is not subset because we will keep zero at place of zero.
so how many total number of subset will be there for any number
Answer2^count(number of set bits)
Now First question is How to generate all possible subset
void generate(int k) {
int num = k;
while (k) {
cout << k << " ";
k--;
k = k & num;
}
cout << 0 << '\n';
}
There are Many Question you can solve using this trick . SOS dp also uses this trick Sos Dp.
Lets see some Question:-
Leetcode Number of Valid Words for Each Puzzle
My Solution of above Questionclass Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
vector<unordered_map<int,int>>mp(26);
for(string & i: words){
int p=0;
for(char j:i){
p |= (1<< (j-'a'));
}
int vis=0;
for(char j:i){
if(!(vis & (1 << (j-'a'))))mp[j-'a'][p]++;
vis |= (1 << (j-'a'));
}
}
vector<int>ans;
for(string &i:puzzles){
int p=0;
for(char j:i){
p |= (1<<(j-'a'));
}
int k=p;
int res=0;
int r=0;
while(k){
r++;
if(mp[i[0]-'a'].count(k))res+=mp[i[0]-'a'][k];
k=(k-1)&p;
}
assert(r==127);
ans.push_back(res);
}
return ans;
}
};
Some Questions To Practice :
CodeChef Chef and Deque
Trick 3
Reducing Time Complexy By factor of B (Depend on your system) Using bitset
Errichto has video on same topic you can watch that
Errichto Video
Practice Question
Codechef Functional Array
Ok now discuss some of Important things related to Bits
--> Gray Code , normaly gray codes are used to check error while sending signals from one place to other place . Gray Code has special property that every consecutive number has atmost one digit different.
Binary Number to gray Codeint g (int n) {
return n ^ (n >> 1);
}
Gray Code to Binary Numberint rev_g (int g) {
int n = 0;
for (; g; g >>= 1)
n ^= g;
return n;
}
--> We can find Minimum XOR of two element in array Just by sorting the array and taking minimum of xor of neighbouring element.
--> To find Maximum XOR of two element We can use trie data structre.
--> We can use Bit mask to solve problems related to "The Inclusion-Exclusion Principle" CP Algorithm Turorial
--> Few Equations Related To Bit Manipulation link
