Given an array A and a range range [0,L] find sum b0+b1+b2+…+bl where bi is the size of largest subset of array whose xor is i. 0<=i<=L
If there is no subset whose xor is i then bi=0.
1<=1000
Please do not ask question of live coding contests for company shortlisting…
@admin People are misusing this platform . I have found 4-5 cases like this… is there anything else other than reporting that can be done in such situations? I think we should ask for reference of problem before answering them may be??
2 Likes
#include<bits/stdc++.h>
using namespace std;
int sumMaxSubsetXOR(int arr[], int n)
{
// Find maximum element in arr[]
int max_ele = arr[0];
for (int i=1; i<n; i++)
if (arr[i] > max_ele)
max_ele = arr[i];
// Maximum possible XOR value
int m = (1 << (int)(log2(max_ele) + 1) ) - 1;
// The value of dp[i][j] is the number of subsets having
// XOR of their elements as j from the set arr[0...i-1]
int dp[n+1][m+1];
int maxS[m+1];
int buf[m+1];
// Initializing all the values of dp[i][j] as 0
for (int i=0; i<=n; i++)
for (int j=0; j<=m; j++) {
dp[i][j] = 0;
maxS[j] = 0;
buf[j] = 0;
}
// The xor of empty subset is 0
dp[0][0] = 1;
// Fill the dp table
for (int i=1; i<=n; i++){
for (int j=0; j<=m; j++) {
int t = j^arr[i-1];
dp[i][j] = dp[i-1][j] + dp[i-1][t];
if (dp[i-1][t]>0) {
if (buf[j] < buf[t] + 1)
maxS[j]=buf[t]+1;
else
maxS[j] = buf[j];
} else if (t==0 && maxS[j] == 0) {
maxS[j] =1;
}
}
for (int j=0; j<=m;j++)
buf[j] = maxS[j];
}
int ans;
for (int i=0; i<=m; i++) {
ans+=maxS[i];
}
return ans;
}
1 Like
You can solve this problem using dp…
You can see that maximum xor of any subset can be 1024 here… Now lets make a table of size N(number of elements) * 1024(upper limit of xor). Basically i,j th element of this table represents size of longest subset that is possible from array[:i] whose xor is j.
Now this table can be filled very easily, dp[i][j] = max(d[i-1][j], dp[i-1][j^a[i]] + 1). Here first term inside max is considering case of longest subset with xor j till i-1 part of array and second term is including ith term of a and taking longest subset in i-1 part of array whose xor is j^a[i] (because a[i]^j^a[i] = j). so that’s it…
After table is filled up, you just have to take summation of last row in table to get answer. Here Time complexity is O(N*2^(ceil(log(Upper limit of Ai) base 2)) = 1000 * 1024.
Hope this will help…
This is where I found the question, don’t blame me without knowing anything.
I don’t even know in which challenge this question has been asked.
@arpit728 Ok… So you were still asking this question on this platform even when “Old Monk” commented there to not answer it hours before you asked same question here… Now I suspect that that profile also belongs to you… 
Please do not try to make people fool… -_-
Last comment on same post link that you shared
I think the expression dp[i][j] = max(d[i-1][j], dp[i-1][j^a[i]] + 1) won’t work when dp[i-1][j^a[i]] =0 because in this case it will not be possible to make the subset of that particular xor.