Maximal AND (Codeforces 1669H)
Tags: Greedy, bitmasks

Let $$$\mathsf{AND}$$$ denote the bitwise AND operation, and $$$\mathsf{OR}$$$ denote the bitwise OR operation.You are given an array $$$a$$$ of length $$$n$$$ and a non-negative integer $$$k$$$. You can perform at most $$$k$$$ operations on the array of the following type:  Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and replace $$$a_i$$$ with $$$a_i$$$ $$$\mathsf{OR}$$$ $$$2^j$$$ where $$$j$$$ is any integer between $$$0$$$ and $$$30$$$ inclusive. In other words, in an operation you can choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) and set the $$$j$$$-th bit of $$$a_i$$$ to $$$1$$$ ($$$0 \leq j \leq 30$$$). Output the maximum possible value of $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ after performing at most $$$k$$$ operations. 

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains the integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$).Then a single line follows, containing $$$n$$$ integers describing the arrays $$$a$$$ ($$$0 \leq a_i < 2^{31}$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing the maximum possible $$$\mathsf{AND}$$$ value of $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ after performing at most $$$k$$$ operations.

Note: For the first test case, we can set the bit $$$1$$$ ($$$2^1$$$) of the last $$$2$$$ elements using the $$$2$$$ operations, thus obtaining the array [$$$2$$$, $$$3$$$, $$$3$$$], which has $$$\mathsf{AND}$$$ value equal to $$$2$$$.For the second test case, we can't perform any operations so the answer is just the $$$\mathsf{AND}$$$ of the whole array which is $$$4$$$.

Sample Inputs:
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1

Sample Outputs:
2
4
2147483646
1073741825

Solution (Python):
import functools
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    r = functools.reduce(int.__and__, a)
    u = [x.count('0') for x in zip(*(f'{x:031b}' for x in a))]
    for (i, x) in enumerate(u):
        if x <= k:
            break
    else:
        print(r)
        continue
    for (i, x) in enumerate(u[i:], i):
        if x <= k:
            r |= 1 << 30 - i
            k -= x
    print(r)

Solution (Python):
from operator import iand
from functools import reduce
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    res = a[0]
    plus = 0
    u = [x.count('0') for x in zip(*(f'{x:031b}' for x in a))]
    for i in range(len(u)):
        if u[i] == 0:
            continue
        if u[i] <= k:
            plus += 2 ** (30 - i)
            k -= u[i]
    res = reduce(lambda x, y: x & y, a)
    print(res + plus)

Solution (Python):
def funl(n, k, l):
    ans = []
    c = 0
    for j in range(30, -1, -1):
        cc = 0
        for i in l:
            if i >> j & 1 == 0:
                cc += 1
        if c + cc <= k:
            ans.append('1')
            c += cc
        else:
            ans.append('0')
    s = ''.join(ans)
    return int(s, 2)
tc = int(input())
for _ in range(1, tc + 1):
    (n, k) = list(map(int, input().split()))
    l = list(map(int, input().split()))
    print(funl(n, k, l))