/
Khaled.java
47 lines (37 loc) · 891 Bytes
/
Khaled.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package infosys;
import java.util.Scanner;
public class Khaled {
public static void main(String[] args) {
@SuppressWarnings("unused")
final int N = 120, M = 1 << 20;
int dp[] = new int[M];
char res[] = new char[M];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
for (int i = 1; i < M; i++)
dp[i] = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
if (arr[i] == 0)
continue;
for (int j = 0; j < M; ++j)
res[j] = 0;
for (int k = 0; k < M; ++k) {
if (res[k] == 1)
continue;
if (dp[k] > dp[k ^ arr[i]])
dp[k] = dp[k ^ arr[i]] + 1;
else if (dp[k ^ arr[i]] > dp[k])
dp[k ^ arr[i]] = dp[k] + 1;
res[k ^ arr[i]] = 1;
}
}
int j = M - 1, k = n >> 1;
while (dp[j] > k)
--j;
System.out.println(j);
sc.close();
}
}