Sherlock and GCD
Sherlock and GCD
marvel32x2 + 2 comments I think the wording for this problem is very unclear. This was one of the more confusing "warmups" to solve, yet the solution was very straightforward.
dheeraj + 5 comments Hi @marvel32x2,
can you please tell us what is confusing about the problem? We will reword it.
jpboon + 1 comment Hi dheeraj,
I don't get this one, can you make it clearer for me what to do? maybe with another example?
Thanks
kmcfetridge89 + 1 comment [deleted]lsoares + 1 comment Euclid
kishancs46 + 2 comments One basic question. Can i rephrase this question like if there is a prime in the given set output YES. ? Reason for my rephrase 1) A single element subset is a valid subset. 2) x>1 x is an element of integer CANNOT divide primes.
jason_goemaat + 1 comment That's not the same question because
{9, 25}
is valid subset that should cause you to printYES
but neither number is prime. Also a single number is a valid subset, but unless it is1
it will not fulfull the criteria because it will be divisible by itself (i.e. a number > 1). For instance the subset{5}
would not cause you to printYES
because all numbers in that set are divisible by 5.challenger29 + 0 comments [deleted]
kiner_shah + 2 comments Take it this way..if the gcd of al nos in the array is >=2 and if the gcd exists in the array itself..den print NO..else print YES
markqn + 0 comments [deleted]codeislife99 + 0 comments Kinda not exactly. You have to take the GCD of the entire array(without duplicates{could use HashSet for not adding them}) and if that GCD>=2 then NO else then YES.
jason_goemaat + 1 comment I think it's a bit confusing with all the numbers and subscripts, plus the samples are allornothing. It would be helpful to have an example like (3, 7, 9, 11). Also don't know what the upsidedown A means...
pmadhukar + 1 comment The upside down A is a set theory symbol which means "for all the elements in the set". So "upside A" 1<=i<=N means "for all i between 1 and N (both inclusive)".
jason_goemaat + 1 comment So if I understand it, that means that for all values of i from 1 to N inclusive, a_{i} will be between 1 and 100,000 inclusive. It seems like that is not an actual constraint on i, which should be listed separately. Reading the constraints now it seems like there is no constraint on i, and if i were N+1 there would be no constraint on a_{i}.
andysctu + 1 comment There IS a constraint on i ...
i must be between 1 and N.
N must be between 1 and 100.
jason_goemaat + 1 comment 1â‰¤aiâ‰¤105âˆ€1â‰¤iâ‰¤N
looks like it's only technically a restraint on ai over a certain range for i. You could also have106â‰¤aiâ‰¤1000âˆ€N<i
couldn't you?andysctu + 1 comment "In the second line there are N spaceseparated integers, a1,a2,â€¦,an, representing the elements of array A."
This implies that 1 <= i <= N
jason_goemaat + 0 comments My points are that it is needlessly complicated, you could just say 1â‰¤a_{i}â‰¤10^{5}.
rayavarapuharik1 + 0 comments no clear explaintion
hantaeyeong + 0 comments There exists no integer x which divides all elements of B
> There exists no integer x which (evenly) divides all elements of B (no residual)
'divides' is not clear word. It would be better to use 'evenly' or 'completely' kind of these words.
You can divide all numbers with the number of x, if x is not zero.
divide doesn't mean natural number.
The problem wants the number x that generates residuals
masterchandigar1 + 0 comments I truly enjoy looking through on this website , it holds fantastic blog posts.
1634810114_coe3b + 0 comments Yes it is really a tricky problem difficult to understand.
sumedhm + 2 comments I think the answer for testcase#16, case 3 is wrong. 27 15015 10010 6006 4290 2730 2310 20020 40040 80080 12012 24024 48048 96096 8580 17160 34320 68640 5460 10920 21840 43680 87360 4620 9240 18480 36960 73920 Since all the numbers except 15015 are even, they will have gcd>=2. Only possibility is 15015 paired with some other no. can be coprimes. But all numbers with 15015 have gcd>1, hence the answer should be "NO", but the answer given is YES. Am I wrong?
gregnelson + 2 comments I get a YES result. 2 is NOT a common denominator for ALL elements in the set, because it is not ALSO a common denominator for 15015 as well. My understanding is that the common denominator found must be common to ALL elements in the set in order to fail the test and provide a NO response...not ALL but 1 element.
sgrebenkin + 0 comments [deleted]sgrebenkin + 0 comments true
sgrebenkin + 0 comments [deleted]
garciaac + 2 comments I struggled with this problem until I discovered these properties of GCD:
 The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
 The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers. (http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties)
So, the gcd over this array [2,6,9,25] can be written as gcd(gcd(gcd(2,6),9),25) which is exactly equal to gcd(gcd(gcd(9,25),6),2) which is exactly equal to gcd(gcd(9,gcd(25,6)),2) which is exactly equal to gcd(gcd(9,2),gcd(25,6)) etc.

This means two things:
 Each permutation of the array does not need to be checked because they all yield the same result. This should help reach an O(n) time complexity.
 If any individual gcd calculation in the chain reaches 1, the entire evaluation will be 1. That means there must exist two numbers in the array which satisfy the conditions of B. Luckily, we don't need to print the contents of B itself.
Hope this helps!
_silent_ + 0 comments Thank u it helped me to get rid of time outs for my solution (:
wangkan2001 + 1 comment How about 6,10,15, GCD of all three is 1, but any two of them has GCD larer than 1
yaseenmollik + 0 comments You didn't get it. Here the set containing all 3 elements gcd is 1. Now try adding more numbers to this set and then calculate gcd of that set. You will always get gcd 1.
rahuja + 3 comments My solution runs fine for all test cases, except 16,17,18,19. I tried to run for 16th. The only test case where my solution differs from given output, is thsi test case:
27 15015 10010 6006 4290 2730 2310 20020 40040 80080 12012 24024 48048 96096 8580 17160 34320 68640 5460 10920 21840 43680 87360 4620 9240 18480 36960 73920
Can anyone point out the applicable subset i this?
rizaozcelik + 0 comments I am having the same problem too. By looking at the test case I can say that the answer should be NO for this since all of the elements except 15015 are even and 15015 is divisible by 5 like many other elements.
jvinniec + 0 comments Same problem here. Unless I misunderstand the conditions I dont see the subset which satisfies the given rules. As mentioned before, since every element except 15015 is even (thus divisible by 2), only a subset with 15015 is valid, but every case fails. Looking at it element by element:
{15015, 10010}  divisible by 5 {15015, 6006}  divisible by 3 {15015, 4290>80080}  divisible by 5 {15015, 12012>96096}  divisible by 3 {15015, 8580>73920}  divisible by 5
So I have to conclude this is a bug unless I'm misunderstanding something in the rules.
shashank21jHackerRank Admin + 5 comments Subset >
{15015, 6006, 10010, 48048,10920,17160,4290,73920}
jvinniec + 1 comment AHA! So I was misunderstanding the instructions. I was interpreting it as "No elements of the subset share a common denominator", but rereading the condition it is quite clear that it's actually "No common denominator shared by all elements (other than 1)". This would make your answer correct. THANK YOU SO MUCH!
shashank21jHackerRank Admin + 0 comments Fun fact: This special test was not there till yesterday. :)
rahuja + 0 comments Thanks. I was just assuming the subsets of length 2. Hence the question.
prajwal_mp + 1 comment but 4804 is not present 48048 is given in input. {15015, 6006,10010, 48048} all elements in this are divisible by 1001.
jvinniec + 1 comment You are correct that 4804 doesnt exist in the list. So instead look at the subset consisting of the first 6 numbers:
15015 10010 6006 4290 2730 2310
There is no integer which divides all of these.
Interestingly, another way to look at this question is to see if there exists a common prime factor amongst all of the entries of the input vector. For instance, in the example above:
15015 6006 10010 48048
are divisible by 1001, but as a consequence they're also divisible by each of the prime factors of 1001 (7, 11, and 13). So you could also check that there is an integer which is not a common prime factor amongst all of the entries of the subset. For the six integers in the example above the prime factors are:
15015 = 3 5 7 11 13 10010 = 2 5 7 11 13 6006 = 2 3 7 11 13 4290 = 2 3 5 11 13 2730 = 2 3 5 7 13 2310 = 2 3 5 7 11
So you can see that there does not exist a single common integer amongst the prime factorizations of each of these numbers. Note, this is obviously a horribly inefficient way to solve this problem and will probably fail some test cases due to timeouts.
prajwal_mp + 0 comments well, thank you.i understand it now.the problem can be solved in O(n).
psy_clops + 0 comments [deleted]KL_170031414 + 2 comments can u help me in the easy way to solve the programming in c
ME_170070079 + 0 comments [deleted]ME_170070079 + 0 comments include
int gcd(int a,int b) { if(b==0) return(a); return(gcd(b,a%b)); } int main() { int t,n,i,j,a[110]; scanf("%d",&t); while(t) { int f=0; scanf("%d",&n); for(i=0;ia[j]) { if(gcd(a[i],a[j])==1) { f=1; goto A; } } else { if(gcd(a[j],a[i])==1) { f=1; goto A; } } } } A: if(f) { printf("YES\n"); } else { printf("NO\n"); } } return(0); }
svaithia + 0 comments Yeah, I agree with others who are saying that wording is confusing. However, it might seem trivial if the wording were straightforward.
Hint:
If for all subset, B, where there is an integer x where x divides all the numbers in the subset B and x is greater than 1, return NO.
Otherwise, return YES.
TheSilentSniper + 1 comment Can this problem be solved in less than O(n^2) time?
dheeraj + 2 comments Yes. O(N)
rjrahul07 + 0 comments [deleted]Holypegasus + 1 comment To me this question boils down to finding if there exists (at least) one mutuallyprime pair in the given list, which involves checking gcd for (up to) all possible pairs. How can one accomplish this in time faster than O(N^2)?
frillyfrufru + 0 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(n1)/2) = O(n^2).]
This problem has a very clear and straightforward solution in a dozen statements.
21region + 2 comments I don't now whether anyone is interested, but there is a way to solve the problem even if you don't know about gcd :
#include <set> #include <iostream> using namespace std; int main() { int T; cin >> T; while (T) { int N; cin >> N; set<int> s; for (int i = 0; i < N; i++) { int a; cin >> a; s.insert(a); } bool divisor_exists = false; for (int d = 2; d <= 100000; d++) { int cnt = 0; for (int a : s) cnt += (a % d == 0); if (cnt == s.size()) { divisor_exists = true; break; } } cout << (divisor_exists ? "NO" : "YES") << '\n'; } }
kishynivas10 + 1 comment such a nice and elegant solution ....can you explain the "for(int a: s)" ......? does it iterate over the set
21region + 0 comments Thank you!
We choose some divisor d and check whether we can divide all of the numbers in a set A. If we can divide all of the numbers, then we cannot choose any of them.
The loop "for (int a : s)" goes through the set A and counts how many of the elements of that set are divisible by d.
asoyyigit + 0 comments Instead of going through 100000, you can iterate until minimum element, which speeds up the process if the minimum element is very low.
jayant_likhar + 1 comment i have a problem with this test case.. 62 69536 36941 43460 86920 4346 60844 93439 30422 93439 4346 19557 95612 54325 47806 39114 95612 93439 86920 43460 6519 52152 65190 78228 95612 84747 8692 65190 69536 10865 78228 2173 65190 30422 28249 13038 99958 52152 17384 99958 19557 58671 4346 56498 82574 28249 45633 56498 2173 43460 54325 54325 93439 10865 80401 39114 60844 34768 15211 6519 89093 99958 15211
ur output: NO my output: YES and subset i got for this is B={69536, 36941}; plz help me for this.
abhiranjan + 2 comments Hi @jayant_likhar, it seems you misread the requirements. Please check again.
jayant_likhar + 1 comment yes i had misread the question. thnk u for the reply.
artud2000 + 1 comment Why did he miss read it?
Never mind got it.
ghsatpute + 1 comment Can anybody mention it so other people can benefit it as well
avnish30jn + 0 comments both are divisible by 41 violating the 2nd rule
shanmuga_priyan + 1 comment There are no elements of B which are equal to another. whats this conditon means???i cant get it properly
Shafaet + 0 comments Each elements of B are unique.
StephnR + 0 comments For those who are confused about the wording:
You should be focused on finding out if the elements in your array (A) have a GCD that is greater than 1.
As mentioned by the moderator: the solution should be O(N)
Huey_Kazahaya + 0 comments For Python3:
#!/bin/python3 import functools as ft def gcd(a,b): if a < b: a,b = b,a if not a % b: return b else: return gcd(b, a % b) for _ in range(int(input())): n = int(input()) array = [int(temp) for temp in input().split()] print('YES' if ft.reduce(gcd, array) == 1 else 'NO')
Hint for it:
If gcd(a,b) = x and gcd(a,b,c) = y, then y = gcd(x,c).
That is, if the array has gcd != 1, then none of its subsets will have gcd == 1. Otherwise, at least one subset will have gcd == 1.
Sort 156 Discussions, By:
Please Login in order to post a comment