Problem in solving Kiljee and XOR problem from hackerearth.

I am assuming you want to know abt this relation:

Dp[i][j] denotes maximum size of subset from first i elements such that its xor is j.

Dp[i][j^arr[i]]=max(dp[i-1][j^arr[i]],dp[i-1][j]+1)

So lets say upto i,i want to find maximum length of subset whose xor is j^arr[i].
So there are two choice ,either u can take arr[i] for this xor or u dont.
If u dont then this value remains unchanged(same as prev),if u do take arr[i],then u will ask whats the maximum length of subset using first i elements whose xor is j.

Base case: dp[0][0]=0 as u can have xor 0 by taking no elements

1 Like