Given N numbers and K, find out if there exists a subset of numbers such that their bitwise xor is K.
Input
First line contains N and K. The second line contains N space-separated integers A1, A2, ..., AN denoting the N numbers.
Output
Output "Yes" if such subset exists, "No" otherwise.(without quotes) Constraints
1 ≤ N ≤ 200
1 ≤ K,Ai ≤ 10^9
Example
Input: 4 101
1 2 100 1000
Output: Yes
Explanation
Example case 1. We can take xor of 1 and 100 to get 101 Note
Bitwise xor of a subset A1, A2, .., AN is equal to (..(A1 xor A2) xor A3).. AN).Each bit of bitwise xor of two numbers is calculated separately. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. For example, bitwise xor of 1(01) and 3(11) is 2 (10).
link for problem: https://www.codechef.com/problems/XORSACK
int dp[201][109*2+1]; // maximum value of xors is max(a[i])*2-1 dp[i][j]=1 if we can build number j with using first i numbers else 0 answere is dp[n][k]
maximum value is 10^9 so the number of columns become of order of 10^9 using normal subset problem how dp[n][109*2+1] is working. could you elaborate.
I think it's 10^9 not 109 ! plz edit it earlier!
but then it would get TLE with a time limit of 1sec. Also it would consume a lot of memory.
Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).
MY BAD GAVE 109 INSTEAD OF 10^9. How can now the problem be solved?
I have a solution for a[i],k < 10^6 (it looks like knapsack problem) you can solve it like this: for (int i = 0; i < n; i++) for (int j = 0; j^a[i] < k; j++) dp[j^a[i]] = (dp[j] == true) ? true : dp[j^a[i]];
with 10^6 as the maximum value of sum the array size would still be order of the order of 200*10^6 which is huge.I think there is some other approach other than the traditional one.
we need only array of size [2][10^6] because dp[i][j] only updates from [i-1][k].
ya space optimisation would do as the answer only depends on the previous state only.
I will only use bitset <1e6> dp and it's only 125KB
it is a better question when we swap xor operation with plus: see it
definitely a good question.
then it would be an implementation of knapsack problem
Again here the sum is of order of 10^9 so dp[i][s] : whether we can form a sum of s using the first i numbers would not pass.
Let's come back to the original question.I think we have to do something with the bitwise representation of the number k as maximum value of 10^9 implies 30 bits to take care of. There would be some reason of having small value of n.
Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).
aliasadiiii said that it is solvable with gauss elimination algorithm in O(N)!! this problem is similar to your
problem.