We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
First, if 1 is an element, then the subset {1} qualifies because there is no integer greater 1 that divides every element of {1}. So assume 1 is not an element. For simplicity, suppose A has three elements: a, b, and c. Clearly, if the gcd of 2 elements in A is 1, say gcd(a, b) = 1, then gcd(a, b, c) must also be one because gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(1, c) = 1. Conversely, let gcd(a, b, c) = 1. Then 1 = gcd(gcd(a,b), c) = gcd(gcd(a,c), b) = gcd(gcd(b,c), a). Obviously if every pair is relatively prime then we are done, so suppose one pair is not relatively prime, say gcd(a, b) != 1. Then this implies that gcd(a, c) = 1 or gcd(b, c) = 1. For suppose on the contrary gcd(a, c) != 1 and gcd(b, c) != 1. Then a = sc for some integer s and b = tc for some integer t, and then 1 = gcd(gcd(a, b), c) = gcd(gcd(sc, tc), c) = c is a contradiction because c cannot be 1 (remember we assumed 1 is not an element of the array). So we've just shown that gcd(A) = 1 if and only if there exists a pair in A that is relatively prime. And the reason why that's important is because computing gcd(a1, a2, ..., an) is O(n) in the number of times we have to compute the gcd of two numbers. [Whereas, as you point out, computing the gcd of every pair in A is O(binomial(n, 2)) = O(n(n-1)/2) = O(n^2).]
This problem has a very clear and straightforward solution in a dozen statements.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and GCD
You are viewing a single comment's thread. Return to all comments →
First, if 1 is an element, then the subset {1} qualifies because there is no integer greater 1 that divides every element of {1}. So assume 1 is not an element. For simplicity, suppose A has three elements: a, b, and c. Clearly, if the gcd of 2 elements in A is 1, say gcd(a, b) = 1, then gcd(a, b, c) must also be one because gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(1, c) = 1. Conversely, let gcd(a, b, c) = 1. Then 1 = gcd(gcd(a,b), c) = gcd(gcd(a,c), b) = gcd(gcd(b,c), a). Obviously if every pair is relatively prime then we are done, so suppose one pair is not relatively prime, say gcd(a, b) != 1. Then this implies that gcd(a, c) = 1 or gcd(b, c) = 1. For suppose on the contrary gcd(a, c) != 1 and gcd(b, c) != 1. Then a = sc for some integer s and b = tc for some integer t, and then 1 = gcd(gcd(a, b), c) = gcd(gcd(sc, tc), c) = c is a contradiction because c cannot be 1 (remember we assumed 1 is not an element of the array). So we've just shown that gcd(A) = 1 if and only if there exists a pair in A that is relatively prime. And the reason why that's important is because computing gcd(a1, a2, ..., an) is O(n) in the number of times we have to compute the gcd of two numbers. [Whereas, as you point out, computing the gcd of every pair in A is O(binomial(n, 2)) = O(n(n-1)/2) = O(n^2).]
This problem has a very clear and straightforward solution in a dozen statements.