PROBLEM LINK :
Author : Asim Krishna Prasad
Tester : Rupesh Maity
DIFFICULTY :
EASY
PREREQUISITES :
Binary numbers
PROBLEM :
Given a particular encoding technique, you have to develop the decoding technique. One important detail is that there can be at most one bit error in the encoded message and the received message.Please read the problem statement for detailed explanation of the problem.
EXPLANATION :
The problem is of observation type. If you run some examples by hand on paper or just look closely at the explained example in the question. You can make following important observations :
 All the bits at position 2^{i} (from right) in the Encoded message, are not part of the original message.
 All the bits of the original message, (that is the bits at the positions which are not 2^{i}, let us call such positions x) contribute to the formation of all the bits at position 2^{i} such that ith bit is set in x.
Let us say position y has got error, which means the yth bit got toggled.
Since no other bit other than y has got error, we can check for the consistency of the encoding algorithm on the received message.
To check the consistency we calculate the value of every 2^{i}th bit, now there are two cases :

Case 1 : the calculated value matches the value of 2^{i}th bit in the received message
In this case, the conclusion is that ith bit is not set in y (or else it must have had caused inconsistency at 2^{i}th bit).

Case 2 : the calculated value doesn't match the value of 2^{i}th bit in the received message
In this case, the conclusion is that ith bit is set in y.
The problem is almost solved at this point. You might want to try the problem once again by yourself. For further solution, read on …
So, the final and most important conclusion from the above observations is that all those 2^{i}th bits in the encoded message will have error such that ith bit is set in y. Once you find all those bits which are set in y, you know the position at which the error has occurred.
Once you have detected the position at which the error has occurred, toggle the value at that position and print all the values which are a part of the original message, i.e, all the positions which are not of type 2^{i}.
EXAMPLE :
Let us run our solution algorithm on the given test case :
R = 10111111101011000 .
We have to check the consistency of all the bold bits.
Now value at position 1 : (sum of bits at position 3, 5, 7, 9, 11, 13, 15, 17) % 2
= (1 + 1 + 1 + 1 + 1 + 1 + 0 + 0) % 2
= 6 % 2
= 0
value at position 2 : (sum of bits at position 3, 6, 7, 10, 11, 14, 15) % 2
= (1 + 1 + 1 + 0 + 1 + 1 + 0) % 2
= 5 % 2
= 1
value at position 4 : (sum of bits at position 5, 6, 7, 12, 13, 14, 15) % 2
= (1 + 1 + 1 + 0 + 1 + 1 + 0) % 2
= 5 % 2
= 1
value at position 8 : (sum of bits at position 9, 10, 11, 12, 13, 14, 15) % 2
= (1 + 0 + 1 + 0 + 1 + 1 + 0) % 2
= 4 % 2
= 0
value at position 16 : (sum of bit at position 17) % 2
= 0 % 2
= 0
We find that there is inconsistency at positions 1, 2, and 8. So, the position of the bit with error has 0^{th}, 1^{st} and 3^{rd} bit set, that is : 1011. Thus the position with error is 11.
Toggle the bit at 11th position, we convert the received message to encoded message, which is : 10111111100011000 .
Now extract the original message : 111110001100.