# Problem in finding size of largest subset with given xor?

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

Nice @arpit728… for down voting my answer… -_-

@admin can we suspend such users from this platform… -_-

@kauts_kanu

This is where I found the question, don’t blame me without knowing anything.

https://cs.stackexchange.com/questions/79705/algorithm-to-find-largest-possible-subset-with-given-xor-value

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… -_-

@kauts_kanu

where did old monk comment.

Last comment on same post link that you shared

#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

@ashishakv27

Explain the approach at least.

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…

@kauts_kanu

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.

@ashishakv27

if (dp[i-1][t]>0)

what is the use of this condition.