The And Problem#12233

The And Problem (Editorial)

listings

Problem Author:	Imran AKKI
Prepared by:	Imran AKKI
Edited by:	Hasan Saleh (MathModel)

Solution We know the fact that for any $x, y \geq 0$ x,y \ge 0 it holds that $x & y \leq min (x, y)$ x \&y \le \min(x,y) because they at the best case share all of the bits.

We want to show that performing the operation sequentially is optimal , because each time the answer will either remain the same or decrease because of definition of AND , i.e. the answer is

x = a_{1} & a_{2} & a_{3} &...& a_{n}

x=a_1 \& a_2 \& a_3 \& ... \& a_n

Let's simulate the process for $n = 3$ n=3

[a_{1}, a_{2}, .., a_{n}] \to [a_{1} & a_{2}, a_{1} & a_{2}, a_{3}] \to [a_{1} & a_{2} & a_{3}, a_{1} & a_{2}, a_{1} & a_{2} & a_{3}] \to [x, x, x]

[a_1,a_2,..,a_n] \rightarrow [a_1\&a_2,a_1\&a_2,a_3] \rightarrow [a_1\&a_2\&a_3,a_1\&a_2,a_1\&a_2\&a_3] \rightarrow [x,x,x]

It's obvious that we cannot do more operations on the array $a$ and that's the minimum possible value , so the optimal answer is $[n times x, x, ..., x]$ [\underbrace{x,x,...,x}_{n\text{ times}}] which is equivalent to perform the operation infinite number of times.

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    A=a[0]
    for i in a:
        A&=i
    print(A)

Python

Complexity $O (n)$ .