AOA - Editorial

bitwise-operatn
gcd

#1

PROBLEM LINK:

Practice

Contest

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