### PROBLEM LINK:

**Author:** Lalit Kundu

**Tester 1:** Minako Kojima

**Tester 2:** Shiplu Hawlader

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

DP, bits

### PROBLEM:

You are given an array A of N integers and an integer K. Your task is to return the maximum possible value of F§ xor K, where P is a subset of A and F§ is defined as a xor of all values in P. If P is empty, then F§ = 0.

### QUICK EXPLANATION:

Since each element of A has a value of at most 1000, we can use dynamic programming dp[i][j] := 1 if and only if there exists a subset P of A[1…i] such that F§ = j. In order to get the result, we return max 1 <= j <= 1023 { dp[n][j] * (j ^ k) }

### EXPLANATION:

Let dp[i][j] := 1 if and only if there exists a subset P of A[1…i] such that F§ = j, otherwise 0

The first observation is that F§ can be at most 1023 since any input number is at most 1000.

Initially we set all dp[i][j] := 0.

Next, we set dp[0][0] := 1, since a xor of the empty set is 0.

We iterate over all elements of A from left to right. For each A[i], we iterate over all possible values of the xor function i.e. a range from 0 to 1023 inclusive and update these values as follows:

```
for i = 1 to N:
for j = 0 to 1023:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
```

The reason for this is that if there exists a subset P of A[1…i - 1] such that F§ = j then there exists also a subset of A[1…i] such that F§ = j or if there exists a subset P of A[1…i - 1] such that F§ = j ^ a[i], then F§ ^ a[i] = j, so there exists a subset P’ of A[1…i] such that F(P’) = j

At the end we have dp[n][j] for all 0 <= j <= 1023, and we can return a maximum value of dp[n][j] * (j ^ k) for all j.

Time Complexity:

The time complexity per one testcase is O(N * 1023);

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

### RELATED PROBLEMS:

To be uploaded soon.