# AOA - Editorial

Practice

Contest

Author: Md Shahid

Tester: Arkapravo Ghosh

Editorialist: Md Shahid

SIMPLE

### PROBLEM:

Given N and array A_i.You need to find AND of ANDs of A_i i.e, X and if GCD(X,1000000007)=1 print X else print -1

### EXPLANATION:

In this problem,you have to find AND of ANDs of the given array A_i.

To do so you have one approach if you are not applying the trick -

``````**INEFFICIENT METHOD**

Input N(size of the array)
Input A(array of size N)
for i=0 to i=N
X=A[i]
for j=i to j=N
X = X & A[j]
if GCD(X,1000000007)==1
print X
else
print -1
``````

This approach will give you TLE(Time limit exceed) because you are using two nested loop so time complexity will be O(n^2).To reduce time complexity you have to use the property of AND

EFFICIENT METHOD

AND of same numbers will give you the same number i.e

1 and 1 and 1 = 1

2 and 2 and 2 = 2

3 and 3 and 3 = 3

In the same way for three numbers 1, 2, 3

(1) and (1 and 2) and (1 and 2 and 3) and (2) and (2 and 3) and (3) =
1 and 2 and 3

``````Input N(size of the array)
Input A(array of size N)
X=A[0]
for i=1 to i=N
X = X and A[i]
if GCD(X,1000000007)==1
print X
else
print -1
``````

Time complexity :- O(n)

### AUTHOR’S, TESTER’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.
Tester’s solution can be found here.

Tags:- ENCODING AOA dshahid380

//