Erasure coding can protect data with less storage overhead than full replication. In the simplest single-parity scheme, one parity block is the bitwise XOR of all data blocks. If any one block is lost, the remaining blocks are enough to reconstruct it.
Design an XorParityRecovery class:
XorParityRecovery() creates a stateless recovery utility.int recover(int[] survivors) returns the value of the one missing block.
survivors contains every block that remains after exactly one block was lost. It may contain data blocks and the parity block, or only data blocks when parity itself was lost. The original position of each block is not provided and is not needed.
XOR every surviving block exactly once and return the result. Each call is independent and must not use an accumulator from an earlier call.
Example 1:
Input:
Output:
Explanation: The original blocks could have been data blocks 3 and 5 with parity 3 XOR 5 = 6. After 5 is lost, 3 XOR 6 reconstructs it.
Example 2:
Input:
Output:
Explanation: 10 XOR 6 = 12, so the missing block is 12. The calculation is identical whether the missing block is data or parity.
Constraints
1 <= survivors.length <= 10^50 <= survivors[i] <= 2^31 - 1- Exactly one block is missing from a valid single-parity group.
- At most
100 calls are made to recover.
Recover a Missing XOR Blockmedium