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.

@vijju123 @meooow

please answer

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??


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

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


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… :expressionless: Please do not try to make people fool… -_-


where did old monk comment.

Last comment on same post link that you shared

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[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++) {

	return ans;
1 Like


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…


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.


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

what is the use of this condition.

@kauts_kanu please answer.