×

# AOA - Editorial

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

This question is marked "community wiki".

203
accept rate: 0%

19.6k349497539

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×307
×93