PROBLEM LINK :Author : Asim Krishna Prasad 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 :
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 :
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 : Now value at position 1 : (sum of bits at position 3, 5, 7, 9, 11, 13, 15, 17) % 2 Toggle the bit at 11th position, we convert the received message to encoded message, which is : 10111111100011000 . Now extract the original message : 111110001100. SOLUTION :asked 07 Mar '16, 01:06
