Editorial - Sherlock and the uncaught Murderer
PROBLEM LINK:
Author: Saurabh Shetty
Tester: Amogh Sinkar
Editorialist: Saurabh Shetty
DIFFICULTY:
MEDIUM
PREREQUISITES:
- XOR Operations
- Binary numbers
PROBLEM:
Sherlock is trying to solve a murder. The murderer is very smart and almost gave his address except his house number that is n. However he over confidently left a clue for Sherlock to solve, that will give the house number n of the murderer.
Sherlock found on the mirror written with red ink “I have some numbers in my mind. All numbers are between 1 and 15.” There are some numbers in the murderer’s mind but, we don’t know how many. Fortunately or unfortunately the murderer left an intriguing array a of size 4 along with a note stating for each i (1<=i<=4) the values in array a[i] correspond to the sum of xors of each number with 2(i-1). Sherlock some how found that the number of odd numbers in the murderer’s mind is d. The murderer then concludes by saying, “find how many numbers are there in my mind, and you shall get me”. Your task is to help Sherlock find how many numbers are there in the murderer’s mind i.e n. This answer is actually the house no of the murderer.
Note:
- The murderer might have a particular number between 1 and 15 more than once in his mind.
EXPLANATION:
Since every number the murderer is thinking is between 1 and 15, we can represent each number between 1 and 15 as sum of some elements from the set of numbers {1, 2, 4, 8}.
Example: 15 = 1+2+4+8, 12 = 4+8, 9 = 1+8
Now Suppose the murderer is thinking of n numbers, Let:
-
p be the number of numbers which use the number 8 from the set for representation as sum of elements from the set. (Or the 4th bit from LSB is high in binary representation).
-
q be the number of numbers which use the number 4 from the set for representation as sum of elements from the set. (Or the 3rd bit from LSB is high in binary representation).
-
r be the number of numbers which use the number 2 from the set for representation as sum of elements from the set. (Or the 2nd bit from LSB is high in binary representation).
-
s be the number of numbers which use the number 1 from the set for representation as sum of elements from the set. (Or the 1st bit from LSB is high in binary representation).
Hence using the above variables we can write four equations:
- 8p + 4q + 2r + (n-s) = a[1]
- 8p + 4q + 2(n-r) + s = a[2]
- 8p + 4(n-q) + 2r + s = a[3]
- 8(n-p) + 4q + 2r + s = a[4]
Now we know how many odd numbers the murderer was thinking of, hence we know the value of s is equal to d.
After solving the 4 equations with 4 variables (as s is known) we get:
n = ( a[4] + a[3] + a[2] - a[1] - (4*d) ) / 13