Hamming code is a 7 digit long code in which digit d0-d4 represent the outermost or in dependent cells and d5-d7 represent the dependent cells. It has a unique property that if you change any digit in a valid hamming code you could find out which digit you changed. b5=(b2+b3+b4)%2 b6=(b1+b3+b4)%2 and b7=b7=(b1+b2+b4)%2

Now suppose if b2 was changed you know b2 was changed because it is independent, but suppose if b5 is changed then you can know which unique(in dependent cell) was changed.

Question alien sort on topological sorting. The question is follows, you are given a set of strings sorted by some manner, you have to find by which manner they are sorted.

As we know that if things are sorted so obviously arr[0]<arr[1], so we can check where these two strings differ, and create a dependency based on it, because arr[0] was before arr[1] for a reason, we check what made arr[0] come before and once we find that out we can create a dependency(in our case edge).

Example: abcd abce adaa checking for abcd and abce: difference on d and e and d comes before so d->e (can be other way also, just depends on the way graph is build) checking for abce and adaa: difference on b and d and b comes before so b->d

Now we do the above operations till we run out of strings and then just do topological sorting based on the dependencies(order) we have created so far.

I was wondering if this question can be done by linked list or not, if you have done it with linked list please share your approach !!

The question might seem vague, but what if input contains 0 while bit manipulation? Well to me it also seemed vague until I put my brain for few hours. You see if we do: (1<<0) = 1

((1<<0)&n) <- we are checking for occurrence of 1 in the input

so how do you check if the input contains 0 or not based on bit manipulation?? because for 0 if we initialize our count with 0 it will collide with 1.

example: if we want to find the highest bit in the following no.

1 12 0 13

if you do what I do, for 0 and 1 you might land at count=0, which is technically wrong.

So how to solve it? well we can start by initializing our count by -1 and doing it +1 after wards. that way all the bits will be shifted and 0 would also have a place.

Sorry for making the spoiler as the question but I am out of names :( So the question, asks to find number of continuous substring such that the number of characters in the substring that has odd frequency is at most one.

I was able to do it in O(n^2) till I saw the editorial and learnt quite few new things! So the naïve approach is creating all the substring and then checking occurrence of characters in it, this cause tle!

Expected approach: take the frequency of characters as bits and manipulate them. Initialize all frequency as 0 and do: freq[i]=freq[i]%2

that way if the character occur odd time freq[i] will be marked 1 and if it occurs even time(or not occurs at all) it will be marked 0. Now create a number from the freq[i].

Now suppose: freq[i+j]=freq[i] (in bit representation)

What does that mean? All the bits are equal, simple?

yes it means that and what else? that all the characters from i to i+j has even frequency(or has not occurred). If we understand that we can build a map to store values of bits and count how much time they occur. Now if we find a number from the map again we know that to do!! Now that is the case when, at most no character is odd, meaning all characters are even but in our case we are given freedom to pick a character that has odd frequency. So our work is not over and we need to do some more things!!

Now we have our bit at freq[i+j] we change at most one bit of it and check for that number!!

Example: freq[i+j]=10101

check for 10101

check for 00101

check for 11101

check for 10001

check for 10111

check for 10100

Why do we check for them? because we are given freedom to have one odd character. considering strings as bits is really a messed up part but it is what it is