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.
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!
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 →
I struggled with this problem until I discovered these properties of GCD:
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!