Hello , ↵
↵
lets start from a basic question that can be solved using Binary number's Knowledge.↵
↵
[LeetCode Poor Pig](https://leetcode.com/problems/poor-pigs/) ||| [Video Solution of Poor Pig](https://youtu.be/4U1ZZYPuXr4)↵
↵
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.↵
↵
<spoiler summary="Solution using Binary number knowledge">↵
let 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) ↵
</spoiler>↵
↵
Trick 1↵
==================↵
↵
We can Hash any string to bit mask .↵
↵
Lets start with simple example :- ↵
↵
Count number of different char in string ↵
↵
<spoiler summary="Using set">↵
We 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();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Using BitMask">↵
~~~~~↵
int count(string & s) {↵
int mask = 0;↵
for (char i : s) {↵
mask |= (1 << (i - 'a'));↵
}↵
return __builtin_popcount(mask);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
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](httphttps://leetcode.com/problems/maximum-product-of-word-lengths/)↵
↵
[Video Editorial](https://youtu.be/CaqzLFT1A0w)↵
↵
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↵
↵
<spoiler summary="Soution Using BitMask">↵
↵
~~~~~↵
class 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;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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↵
↵
<spoiler summary="Answer">↵
2^count(number of set bits)↵
</spoiler>↵
↵
↵
↵
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](https://codeforces.net/blog/entry/45223).↵
↵
Lets see some Question:-↵
↵
↵
[Leetcode Number of Valid Words for Each Puzzle](https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/)↵
↵
<spoiler summary="My Solution of above Question">↵
↵
~~~~~↵
class 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;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Some Questions To Practice :↵
↵
[CodeChef Chef and Deque](https://www.codechef.com/problems/CHEFDQE)↵
↵
↵
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](https://www.youtube.com/watch?v=jqJ5s077OKo)↵
↵
Practice Question↵
↵
[Codechef Functional Array](https://www.codechef.com/problems/FUNARR)↵
↵
↵
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.↵
↵
<spoiler summary="Binary Number to gray Code">↵
↵
~~~~~↵
int g (int n) {↵
return n ^ (n >> 1);↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Gray Code to Binary Number">↵
↵
~~~~~↵
int rev_g (int g) {↵
int n = 0;↵
for (; g; g >>= 1)↵
n ^= g;↵
return n;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
--> 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](https://cp-algorithms.com/combinatorics/inclusion-exclusion.html)↵
↵
--> Few Equations Related To Bit Manipulation [link](https://codeforces.net/blog/entry/94447)↵
↵
My YouTube Channel :- [YouTube](https://www.youtube.com/channel/UCHCGL-xmIy_Hm7fjfG697Bg)↵
↵
lets start from a basic question that can be solved using Binary number's Knowledge.↵
↵
[LeetCode Poor Pig](https://leetcode.com/problems/poor-pigs/) ||| [Video Solution of Poor Pig](https://youtu.be/4U1ZZYPuXr4)↵
↵
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.↵
↵
<spoiler summary="Solution using Binary number knowledge">↵
let 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) ↵
</spoiler>↵
↵
Trick 1↵
==================↵
↵
We can Hash any string to bit mask .↵
↵
Lets start with simple example :- ↵
↵
Count number of different char in string ↵
↵
<spoiler summary="Using set">↵
We 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();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Using BitMask">↵
~~~~~↵
int count(string & s) {↵
int mask = 0;↵
for (char i : s) {↵
mask |= (1 << (i - 'a'));↵
}↵
return __builtin_popcount(mask);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
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](
↵
[Video Editorial](https://youtu.be/CaqzLFT1A0w)↵
↵
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↵
↵
<spoiler summary="Soution Using BitMask">↵
↵
~~~~~↵
class 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;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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↵
↵
<spoiler summary="Answer">↵
2^count(number of set bits)↵
</spoiler>↵
↵
↵
↵
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](https://codeforces.net/blog/entry/45223).↵
↵
Lets see some Question:-↵
↵
↵
[Leetcode Number of Valid Words for Each Puzzle](https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/)↵
↵
<spoiler summary="My Solution of above Question">↵
↵
~~~~~↵
class 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;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Some Questions To Practice :↵
↵
[CodeChef Chef and Deque](https://www.codechef.com/problems/CHEFDQE)↵
↵
↵
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](https://www.youtube.com/watch?v=jqJ5s077OKo)↵
↵
Practice Question↵
↵
[Codechef Functional Array](https://www.codechef.com/problems/FUNARR)↵
↵
↵
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.↵
↵
<spoiler summary="Binary Number to gray Code">↵
↵
~~~~~↵
int g (int n) {↵
return n ^ (n >> 1);↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Gray Code to Binary Number">↵
↵
~~~~~↵
int rev_g (int g) {↵
int n = 0;↵
for (; g; g >>= 1)↵
n ^= g;↵
return n;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
--> 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](https://cp-algorithms.com/combinatorics/inclusion-exclusion.html)↵
↵
--> Few Equations Related To Bit Manipulation [link](https://codeforces.net/blog/entry/94447)↵
↵
My YouTube Channel :- [YouTube](https://www.youtube.com/channel/UCHCGL-xmIy_Hm7fjfG697Bg)↵
