Hello ,
lets start from a basic question that can be solved using Binary number's Knowledge.
LeetCode Poor Pig ||| Video Solution of 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.
Trick 1
We can Hash any string to bit mask .
Lets start with simple example :-
Count number of different char in string
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
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
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
Some Questions To Practice :
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
Practice Question
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.
--> 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
My YouTube Channel :- YouTube
Auto comment: topic has been updated by __LOOSER__ (previous revision, new revision, compare).
I have some comments about formatting and punctuation. Right now, you're being quite chaotic to the point where it actually impedes readability. Here are some basic tips.
Tips specific to writing in Codeforces:
Tips specific to your blog:
There are also some problems with clumsy sentence structures, but it's hard to teach something simple about them.
I have taken the liberty of rewriting your blog with these things in mind. Some things still don't quite make sense to me, so I have written some comments as well. They are in italics and square brackets.
Hello.
Let's start from a basic question that can be solved using knowledge of binary numbers: LeetCode Poor Pigs (video solution)
Basically, in the question above you are given $$$n$$$ poison bottles, and you can do $$$t$$$ trials. How many pigs do you need to find the bottle with the poison? [This sentence still doesn't make sense. What is a trial? You're not sharing the important details of the problem, thus a reader will have to read the LeetCode problem anyway. But if they do, what is the point of summarizing like this? Also, there aren't $$$n$$$ poison bottles. Only one bottle has the poison. The rest are just bottles.]
Let's say there are 2 bottles and one trial. How many pigs do we need then? One, because we can feed the first bottle to pig 1. If it dies, then the poison is in bottle 1, otherwise, the poison is in bottle 2.
We can generalize the idea above using binary numbers. How?
Let's number the bottles from $$$1$$$ to $$$n$$$. Consider the poison bottle. I want to know whether the first digit in its binary representation is 1 or 0. To do that, I will feed pig 1 all bottles whose first digit is 1 (that is, 1, 3, 5, ...). If pig 1 dies, then the first digit is 1, otherwise it is 0. The same process can be repeated for other digits.
If we have more than 1 trial (let's say 2) we can use ternary numbers instead of binary numbers. [How?]
This way we see that the answer is $$$\lceil \log_{t + 1} (n) \rceil$$$. [This is not really a full solution, since there is no proof that we can't do it with less pigs]
Trick 1
We can hash any string to a bitmask. [This is not really hashing.]
Let's start with a simple example: counting the number of different characters in a string.
We can use a set or a boolean array to count the characters.
We can use this trick to reduce the constant factor by 26 in many different kinds of problems. Let's take an example: LeetCode Maximum Product of Word Lengths (video editorial).
If you try to solve this question using a boolean array the time complexity will be $$$O(26n^2)$$$ which will lead to a TLE. However, you can improve the time complexity to $$$O(n^2)$$$ simply by using a bitmask.
Trick 2
Printing all subsets of $$$K$$$. What do I mean by subset? Let's say we have a number whose binary representation is 1011. We keep the 0s as they are, but any 1 can be made into a 0 or kept as a 1. The subsets of 1011 are 0011, 1010, 1011 and so on. 1100 is not a subset because the 0 has turned into a 1.
How many total number of subsets does a given number have?
$2^{\text{number of set bits}}
Now, the first question is — how to generate all possible subsets?
[Interesting. How/why does it work?] There are many questions you can solve using this trick. SOS DP also uses this trick. [It doesn't.]
Let's see an example question: LeetCode Number of Valid Words for Each Puzzle.
A question to practice: CodeChef Chef and Deque.
Trick 3
Reducing time complexity by a factor of $$$B$$$ (depending on your system) using bitsets. [What is $$$B$$$ and how does it depend on my system?]
Errichto has a video on this topic.
A practice question: CodeChef Functional Array.
More facts
Now let's discuss some other important things related to bits.
int rev_g (int g) { int n = 0; for (; g; g >>= 1) n ^= g; return n; }
How much time did you took to write this comment ?
Thank you for pointing out my mistake. From next time I will try to look into it and validate it before posting the blog.
Also from next time I will fix my audio in youtube videos and try to make video noise free.
Again thank you for your time to pointing out mistake.