This is a dynamic programming problem with three state parameters: your current position in the array, how many elements you have chosen, and the XOR of the chosen elements.

Since the array does not change, you don't need to recalculate values you have memoized already.

The recurrence relation looks like this:

dp(pos, rem, xor) = min(dp(pos - 1, rem, xor), dp(pos - 1, rem - 1, xor ^ a[i]))

See the implementation below for more detail.

Since the maximum value for XOR is 210 - 1, there can be 210 * N * K states. Thus the solution complexity is O(210 * N * K).


66% Solution Ratio
exsurrealEarliest, Oct '16
Kuddus.6068Fastest, 0.0s
exsurrealLightest, 393 kB
monna4335Shortest, 383B
Toph uses cookies. By continuing you agree to our Cookie Policy.