Short Problem Definition:
Sherlock is stuck while solving a problem: Given an array A={a1,a2,..aN}, he wants to know if there exists a subset, B={ai1,ai2,…aik} where 1≤i1<i2<…<ik≤N…
Link
Complexity:
time complexity is O(N);
space complexity is O(1)
Execution:
A subset has no common divisor if the GCD equals 1. There is an interesting fact that leads to my solution: If any subset has GCD 1, any bigger set containing this set will also have GCD 1. Therefore GCD(a,b,c,d) = GCD(GCD(GCD(a,b),c),d). This is easily generated by python reduce.
Beware: The problem statement allows n==1.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#!/usr/bin/py def gcd(a, b): if a % b = = 0 : return b else : return gcd(b, a % b) def multiple_gcd(numbers): return reduce ( lambda x,y: gcd(x,y), numbers) if __name__ = = '__main__' : t = input () for _ in xrange (t): n = input () values = map ( int , raw_input ().split()) if len (values) < 2 : print "NO" continue if (multiple_gcd(values) = = 1 ): print "YES" else : print "NO" |