### PROBLEM LINK:

**Author:** Md Shahid

**Tester:** Arkapravo Ghosh

**Editorialist:** Md Shahid

### DIFFICULTY:

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*
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*
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