text: Given
  Given
  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??
  #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; }
  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… -_-
  where did old monk comment.
  Last comment on same post link that you shared
  Explain the approach at least.
  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.