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.
The problem here is essentially to identify, given certain constraints, whether there exists a subset of an array
�
Check here the following rules:
It must be a non-empty subset (
�
′
A
′
).
There doesn’t exist an integer
�
x which divides all elements of
�
′
A
′
.
There are no elements in
�
′
A
′
that are equal to another.
Let's derive a solution:
For rule 3, it's evident that all elements in the array
�
A must be unique for any subset
�
′
A
′
to adhere to it.
Rule 2 is the most complex condition to validate. However, if we observe, it's impossible for two co-prime numbers to have a common divisor (other than 1). Therefore, the existence of just two co-prime numbers in
�
A automatically validates condition 2 for any subset
In the sample input provided:
Copy code
3
3
1 2 3
2
2 4
3
5 5 5
For test case 1: [1, 2, 3] contains co-prime numbers (1 and 2, or 1 and 3, or 2 and 3). So, it outputs "YES".
For test case 2: [2, 4] does not contain any pair of co-prime numbers. So, it outputs "NO".
For test case 3: [5, 5, 5] has duplicate elements. So, it outputs "NO".
�
′
A
′
containing them.
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 →
The problem here is essentially to identify, given certain constraints, whether there exists a subset of an array � Check here the following rules:
It must be a non-empty subset ( � ′ A ′ ). There doesn’t exist an integer � x which divides all elements of � ′ A ′ . There are no elements in � ′ A ′ that are equal to another. Let's derive a solution:
For rule 3, it's evident that all elements in the array � A must be unique for any subset � ′ A ′ to adhere to it. Rule 2 is the most complex condition to validate. However, if we observe, it's impossible for two co-prime numbers to have a common divisor (other than 1). Therefore, the existence of just two co-prime numbers in � A automatically validates condition 2 for any subset In the sample input provided:
Copy code 3 3 1 2 3 2 2 4 3 5 5 5 For test case 1: [1, 2, 3] contains co-prime numbers (1 and 2, or 1 and 3, or 2 and 3). So, it outputs "YES". For test case 2: [2, 4] does not contain any pair of co-prime numbers. So, it outputs "NO". For test case 3: [5, 5, 5] has duplicate elements. So, it outputs "NO". � ′ A ′ containing them.