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.
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:
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.
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 →
You are correct that 4804 doesnt exist in the list. So instead look at the subset consisting of the first 6 numbers:
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:
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:
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.