# HackerRank ‘Sherlock and GCD’ Solution

H
##### 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…

Sherlock and GCD

##### 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"` 