Maximum AND (Codeforces 1721D)
Tags: Greedy, divide and conquer

You are given two arrays $$$a$$$ and $$$b$$$, consisting of $$$n$$$ integers each.Let's define a function $$$f(a, b)$$$ as follows:   let's define an array $$$c$$$ of size $$$n$$$, where $$$c_i = a_i \oplus b_i$$$ ($$$\oplus$$$ denotes bitwise XOR);  the value of the function is $$$c_1 \mathbin{\&} c_2 \mathbin{\&} \cdots \mathbin{\&} c_n$$$ (i.e. bitwise AND of the entire array $$$c$$$). Find the maximum value of the function $$$f(a, b)$$$ if you can reorder the array $$$b$$$ in an arbitrary way (leaving the initial order is also an option).

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of arrays $$$a$$$ and $$$b$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$).The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < 2^{30}$$$).The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print one integer — the maximum value of the function $$$f(a, b)$$$ if you can reorder the array $$$b$$$ in an arbitrary way.


Sample Inputs:
3
5
1 0 0 3 3
2 3 2 1 0
3
1 1 1
0 0 3
8
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Sample Outputs:
2
0
7

Solution (Python):
import sys
from collections import defaultdict

def input():
    return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = 0
    bit = max(max(A), max(B)).bit_length()

    def check(res):
        cnt = defaultdict(int)
        for x in A:
            cnt[x & res] += 1
        for x in B:
            cnt[~x & res] -= 1
        return all((v == 0 for v in cnt.values()))
    for i in range(bit - 1, -1, -1):
        if check(res | 1 << i):
            res |= 1 << i
    print(res)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        main()

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def check(pre):
        cnt = defaultdict(int)
        for x in a:
            x &= pre
            cnt[x] += 1
        for x in b:
            x &= pre
            x ^= pre
            cnt[x] -= 1
            if cnt[x] == 0:
                del cnt[x]
        return len(cnt.keys()) == 0
    ans = 0
    for j in range(29, -1, -1):
        ans |= 1 << j
        if check(ans) is False:
            ans ^= 1 << j
    print(ans)
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
from collections import Counter
m = int(input())

def solve(n: int, a: list, b: list) -> None:
    ans = 0
    for digit in range(29, -1, -1):
        t = ans | 1 << digit
        cnt_a = Counter((x & t for x in a))
        cnt_b = Counter((x & t for x in b))
        flag = True
        for x in cnt_a.keys():
            if cnt_a[x] != cnt_b[x ^ t]:
                flag = False
                break
        if flag:
            ans = t
    print(ans)
while m > 0:
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    solve(n, a, b)
    m -= 1