[Codeforces Round #784 (Div. 4)] H. Maximal AND

 

 

---

※. 작업을 통해 ai의 비트 중에 비트 1개를 1로 바꿀 수 있다.(or 연산)

※. 가장 최상위 비트부터 바꾸는 것이 이득이다. (j = 2, 4 ,8을 바꾸는 거 보다 j = 16을 바꾸는 것이 더 큰 값)

※. 1에서 n개 까지의 배열값에서 (0~30)번째 비트가 1인것의 개수를 세어준다.

(비트가 겹친다면 k작업을 적게 수행하여 결과를 바꿀 수 있다.)

※. (n - (0~30)비트 개수를 저장한 배열)이 k보다 작다면 결과값을 바꿀 수 있다.

(n = 3, k = 2,  [8,4,2]이면 arr[0] = 0, arr[1] = 1, arr[2] = 1, arr[3] = 1이다. 3 - 1(arr[3])은 2이므로 k작업을 2번해서 4와 2를 모두 or 8 (100 -> 1100, 10 -> 1010)으로 바꿀 수 있고 and 연산으로(1000 & 1100 & 1010 = 1000 결과 : 8 가장 큰 값을 구할 수 있다.)

※. 비트가 움직이지 않은 {1} 도 비트 개수를 구해줘야 한다.

([5,1,3] 이고 k가 0일때 arr[0]을 구하지 않으면 결과가 1이 나오지 않는다.)

 

1. 배열값 a를 받으면 j번째 비트(0~30)까지 1인 비트의 개수를 저장해주는 배열을 만든다.

2. 최상위 비트(30번째)부터 k작업보다 같거나 적게 (n - (현재비트 개수))를 수행할 수 있는지 판별한다.

3. 수행할 수 있다면 result값에 (1 << (현재비트))만큼 더해준다.

(작업은 비트 1개만 1로 바꿀 수 있으므로 현재비트만 더해준다. 임의의 비트가 n번만큼 있다면 k작업을 수행하지 않더라도 임의의 비트만큼 결과값이 나온다.)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			int[] arr = new int[31];
			st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < n; i++) {
				int a = Integer.parseInt(st.nextToken());
				for(int j = 0; j < 31; j++) {
					if((a & (1 << j))> 0) {
						arr[j]++;
					}
				}
			}
			int result = 0;
			for(int i = 30; i >= 0; i--) {
				int need = n - arr[i];
				if(need <= k) {
					k -= need;
					result += (1 << i);
				}
			}
			sb.append(result).append('\n');
		}
		System.out.println(sb);
	}
}