Sherlock and Gcd Hackerrank Solution in Python 3
Hackerrank Solution: Sherlock and GCD
Original Problem
Sherlock is stuck while solving a problem: Given an array \(A=\{a_1,a_2, ...a_N\}\), he wants to know if there exists a subset \(B\) of this array which follows these statements:
- \(B\) is a non-empty subset.
- There exists no integer \(x (x>1)\) which divides all elements of \(B\).
- There are no elements of \(B\) which are equal to another.
Input Format
The first line of input contains an integer, \(T\), representing the number of test cases. Then \(T\) test cases follow.
Each test case consists of two lines. The first line contains an integer, \(N\), representing the size of array \(A\). In the second line there are \(N\) space-separated integers, \(a_1, a_2, ..., a_N\), representing the elements of array \(A\).
Constraints
\(1\leq T\leq 10\)
\(1\leq N\leq 100\)
\(1\leq a_i \leq 10^5\; \forall 1\leq i\leq N\)
Output Format
Print YES if such a subset exists; otherwise, print NO.
Sample Input
3 3 1 2 3 2 2 4 3 5 5 5 Sample Output
YES NO NO Explanation
In the first test case, \( \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\} \) and \(\{1,2,3\}\) are all the possible non-empty subsets, of which the first and the last four satisfy the given condition.
For the second test case, all possible subsets are \(\{2\}, \{4\}, \{2,4\}\). For all of these subsets, \(x=2\) divides each element. Therefore, no non-empty subset exists which satisfies the given condition.
For the third test case, the following subsets exist: \(S_1=\{5\}, S_2=\{5,5\}\) and \(S_3=\{5,5,5\}\). Because the single element in the first subset is divisible by 5 and the other two subsets have elements that are equal to another, there is no subset that satisfies every condition.
Solution
That's a really interesting problem! The crucial hint lurks in the title of the problem: The greatest common divisor (GCD). According to the problem statement, all elements of \(B\) have to be coprime. That is, there must be no \(x\in\mathbb{N}_{>1}\), which divides all elements of \(B\). If \(B\subseteq A\), then \(\gcd(A)\leq \gcd(B)\), since every element of \(A\) which is not in \(B\) either leaves the GCD unchanged, which is also the case with duplicates, or it reduces the gcd. So, if \(k=\gcd(A)\), it means that \(k\) divides all elements of \(A\). But since all the elements of \(B\) are contained in \(A\), \(k\) therefore divides all elements of \(B\). It follows that if all elements of \(A\) are coprime, there exists a subset \(B\), as long as set \(A\) is not empty.
When it comes to the implementation of the GCD of a set of three or more elements, we could calculate the product of prime factors common to all the numbers, or calculate the GCD repeatedly by taking the GCDs of pairs of numbers, such that:
\[\gcd(A) = \gcd(a_1, a_2, a_3, ..., a_N) = \gcd(\gcd(a_1, a_2), a_3, ..., a_N)\]
This is exactly what happens when you use Ruby with it's functional reduce method and the internal gcd callback. This allows us to complete this task with this tiny snippet:
gets.to_i.times{ n = gets.to_i a = gets.split.map(&:to_i) if n > 1 and a.reduce(&:gcd) == 1 puts "YES" else puts "NO" end } « Back to problem overview
Sherlock and Gcd Hackerrank Solution in Python 3
Source: https://www.xarg.org/puzzle/hackerrank/sherlock-and-gcd/