Author: Md Shahid
Tester: Arkapravo Ghosh
Editorialist: Md Shahid
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
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
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 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