There are $64$ hard drives each with one extra bit ("flag"), the value of which you don't know (it can be '$0$' or '$1$'). One hard drive is infected with virus that you need to heal.

You have two softwares in your disposal to help you: a detector and an antivirus. The detector always identifies the infected hard drive, but may only set/unset one flag (out of the $64$ flags) and can peek to see the values of each flag. The antivirus can inspect each flag as well, but may only attempt to heal one hard drive. If the antivirus is given a clean hard drive it stays clean, and if it is given an infected one it heals it.

How would you coordinate the work of the detector and the antivirus such that you always fulfill your objective?


Because the original question and answer of this dupe are a bit.. hard to read, I'll try to write up a simpler solution:

First, the detector identifies the borkened drive. Then it

enumerates the disks from 0 to 63, and XORs (bitwise) together all the disk numbers that have their flag bit set to 1.

This gives some result

from 0 to 63, which the decoder can always change into any other result by flipping only one disk's flag bit: the numbers from 0 to 63 represent all possible 6 bit sequences, which is useful, because XORring works by flipping bits that correspond to 1s in the other operand, so any combination of bits can be flipped as desired.

For example,

Let's say that the XORring resulted in 13, and the broken disk was 27. The detector wants to set the total XOR to 27, so it can now compute (using the property of XOR that adding a XOR is the same operation as removing a XOR) $27 \ominus 13 = 27 \oplus 13 = 22$, and flip the flag on the 22nd disk.

The antivirus can now

calculate the XOR of all disk numbers with the flag set to 1, and it will end up with the number of the broken disk, 27, because $13 \oplus 22 = 27$.

  • $\begingroup$ Ideally you'd put improved solutions on the dup target, not on the dup post where it's likely to be ignored. $\endgroup$ – Rubio Jun 24 at 11:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.