__LOOSER__'s blog

By __LOOSER__, history, 19 months ago, In English

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

Video Editorial

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 :

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __LOOSER__ (previous revision, new revision, compare).

»
19 months ago, # |
Rev. 2   Vote: I like it +91 Vote: I do not like it

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.

  • There is a space after and no space before all of the following: ,.;:?!
  • Sentences start with a capital letter.
  • Sentences end end with a period, exclamation mark, question mark or ellipsis.
  • In English, capital letters should only be used in names, beginnings of sentences and to express extreme frustration. Don't capitalize random words in the middle of a sentence.
  • Try to avoid writing too many paragraphs that are too short or too long. 4-12 lines on a normal screen is the optimal paragraph length.

Tips specific to writing in Codeforces:

  • Familiarize yourself with the syntax for formatting. It's much nicer to use the "built-in" bulleted lists than to try to write your own with "->".
  • Math is best written with Latex. You can put math symbols between dollar signs.
  • H1 is too big to use more than once in a blog. I'd use 3 or even 4 #-s before a title.

Tips specific to your blog:

  • "Bitmask" is one word and the M is not capitalized.
  • Consistency is good. It's fine to write either "XOR" or "xor", but once you have picked one you should stick to that.

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.

Your blog, rewritten
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How much time did you took to write this comment ?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.