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

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

@vijju123 @meooow

please answer

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

@kauts_kanu

where did old monk comment.

Last comment on same post link that you shared

@ashishakv27

Explain the approach at least.

@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.

@kauts_kanu please answer.