HackerRank Sherlock and GCD challenge

Question

I've written an implementation for the Sherlock GCD HackerRank Challenge. As the running time of my algorithm is something like \$O(kn^2)\,ドル I reckon that there's a more efficient algorithm that could be used instead. Are there any improvements that can be made to my implementation to reduce the running time?

Problem statement (as shown on HackerRank)

Sherlock is stuck while solving a problem: Given an array \$A={a1,a2,⋯,aN}\,ドル he wants to know if there exists a subset \$B\$ of this array which follows these statements:

1. \$B\$ is a non-empty subset.
2. There exists no integer \$x(x>1)\$ which divides all elements of \$B\$.
3. There are no elements of \$B\$ which are equal to another.

Print YES if such a subset exists; otherwise, print NO

Answer:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class SherlockGCD {
 public static void main(String[] args) {
 try(BufferedReader input = new BufferedReader(new InputStreamReader(System.in))){
 int numTestCases = Integer.parseInt(input.readLine());
 for(int i = 0; i < numTestCases; i++){
 int N = Integer.parseInt(input.readLine());
 String[] array = input.readLine().split(" ");
 Set<Integer> distinctElements = new HashSet<>(N);
 for(int j = 0; j < N; j++){
 distinctElements.add(Integer.valueOf(array[j]));
 }
 List<Integer> numbers = new ArrayList<>(distinctElements);
 System.out.println(doesSubsetExist(distinctElements, numbers));
 }
 }catch(IOException e){
 e.printStackTrace();
 }
 }
 /**
 * Determines whether a subset that satisfies the constraints in the problem statement exists.
 *
 * Looks for two elements that satisfy the conditions set out in the problem statement. If two such
 * elements exist, then there exists at least one subset that satisfies the conditions. Else, there doesn't exist a
 * subset.
 *
 * @param set A set of distinct numbers. Passed in because .contains() is O(1) for a Set vs O(n) for an
 * ArrayList
 * @param numbers A list of distinct numbers
 * @return "YES" if such a subset exists. "NO" if not.
 */
 private static String doesSubsetExist(Set<Integer> set, List<Integer> numbers){
 if(set.contains(1)){
 return "YES";
 }
 // If there's only one distinct element and that element isn't the integer 1, then the second constraint is not
 // satisfied.
 if(numbers.size() == 1){
 return "NO";
 }
 for(int i = 0; i < numbers.size(); i++){
 for(int j = i + 1; j < numbers.size(); j++){
 for(int k = 2; k <= Math.min(numbers.get(i), numbers.get(j)); k++){
 if(numbers.get(i) % k == 0 && numbers.get(j) % k == 0){
 break;
 }
 if(k == Math.min(numbers.get(i), numbers.get(j))){
 return "YES";
 }
 }
 }
 }
 return "NO";
 }
}

Answer 1

There is a simple efficient solution for this problem which uses the following observation: if \$ A ⊆ B \,ドル then \$ \gcd(A) ≥ \gcd(B) \$. Proof: if \$ g = \gcd(B) \$ then \$ g \$ divides all elements of \$ B \$. But all elements from \$ A \$ are in \$ B \,ドル thus \$ g \$ divides all elements in \$ A \$. Hence, \$ \gcd(A) ≥ g \$.

This means that we can simply check that the GCD of all elements of the given array is \$ 1 \$.

What about duplicates? They don't matter because they do not affect the value of the greatest common divisor.

How to compute the GCD of an array? We can use the following property: $$ \gcd(a_0, a_1, a_2, \dotsc, a_{n - 1}) = \gcd(\gcd(a_0, a_1), a_2, \dotsc, a_{n - 1}). $$ To compute the GCD of two numbers one can use Euclid's algorithm.

The time complexity is \$ O(n + \log \max A) \,ドル where \$ \max A \$ is the maximum element of the array \$A\$.

• Evan Bechtol: Nice proof! Also immensely improves the run-time compared to OP's.

Answer 2

As a super-quick not-algorithm-related review :

• return type for doesSubsetExist should probably be some kind of boolean, not string.

• doesSubsetExist should probably just take a list of number as an argument. The set can be constructed as part of doesSubsetExist. The will make the interface clearer and as close as possible to the way the problem is given.