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