PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Given n numbers, find if a given number can be represented as a bitwise xor sum of some subset from the n numbers.
QUICK EXPLANATION:
We use gaussian elimination to check if the given number can be represented as a linear combination of bit wise vector corresponding to n numbers.
EXPLANATION:
Step - 1 : We need to find a clever way to represent numbers.
The operations that we are doing here are bitwise xor. One obvious representation would be vector of bits.
What will be bitwise xor of two number correspond to operations on bit-vectors ?
Addition modulo 2.
Step - 2 : Subset sum is equivalent to linear combination here.
K can be represented as sum of subset of bit-vectors iff if it can be represented as a linear combination of the N bit-vectors. Note that all additions of bit-vectors are modulo 2 here. If we can represent K as a linear combination, the coefficients can also be taken modulo 2. We get a subset by doing this. If we already have a subset, we have already obtained the linear combination.
Step - 3 : Checking if K’s bit-vector is a linear combination of the given N bit-vectors
If K’s bit vector can be represented as a linear combination of N bit-vectors, the rank of the N bit vectors is equal to the rank of N bit vectors + K’s bit vector.
Step - 4 : We should find rank of a set of bit vectors
We use Gaussian Elimination in this step. After Gaussian Elimination, rank is equal to non zero rows.
Please refer to Author’s solution for clever implementation of gaussian elimination for bit vectors.
AUTHOR’S SOLUTION:
Author’s solution can be found here.
Tester’s solution can be found here.