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.

**Solution using Binary number knowledge**

# Trick 1

We can Hash any string to bit mask .

Lets start with simple example :-

Count number of different char in string

**Using set**

**Using BitMask**

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 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

**Answer**

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 Question**

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.

**Binary Number to gray Code**

**Gray Code to Binary Number**

--> 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