|
Given a set S of having numbers 1, 2, 3, . . ., N, and an integer K, the task is to form a set A by taking K values from S such that any pair formed by taking one value from S and another from A, is always coprime. (Two numbers are coprime if their GCD is 1).
Note: If multiple solutions exist, print any of them, and if no such set exists, print -1.
Examples:
Input: N = 4, K = 1
Output: 1
Explanation: We can choose [1] for set A and remaining numbers
[2, 3, 4] contained in set S. 1 is coprime with 2, 3 and 4 so the condition is satisfied.
Input: N = 4, K = 2
Output: 1 3
Approach: The problem can be solved based on the following observation:
Let’s focus on prime numbers since the gcd function works on primes independently of other primes.
- Consider all primes p such that p ∗ 2 ≤ N. Hence, 2 and p must be in same component for all primes ≤ N / 2. Let’s add this to a set called X.
- All non-prime integers shall also lie in the same set as their prime factors. So any integer > 1 which is not a prime shall also be added to this X.
We can claim that the elements present in X shall all be in either S or A.
- For example, for S = 13, the primes less than 6.5 are 2, 3, 5, so the set S formed is [2, 3, 4, 5, 6, 8, 9, 10, 12]. Elements not present in this set are 1 and all primes greater than N/2. Let’s say there are C such elements. For N = 13, we have [1, 7, 11, 13]. C = 4 here.
- So, if we can add elements from [1, 7, 11, 13] to make a set of size K or size N − K, then it is possible to find such S and A.
- It is only when we have either K ≤ C or K ≥ N−C that we can form set S and A.
The list of primes can be computed using the sieve of Eratosthenes.
Follow the steps mentioned below to implement the idea:
- Find the primes within the range provided above.
- Now check the value of C and N-C.
- Compare that with K as per the conditions mentioned.
- If the conditions are satisfied then form the sets, otherwise, no such set is possible.
Below is the implementation of the above approach:
C++
<?php
function findSet($n, $k)
{
$dp = array_fill(1, $n + 1, -1);
$dp[1] = 0;
$together = 0;
$single = 1;
for ($i = 2; $i <= $n; $i++) {
if ($i % 2 == 0 && $dp[$i] == -1) {
$dp[$i] = 1;
$together++;
} else if ($dp[$i] == -1) {
$z = 2 * $i;
$flag = -1;
while ($z <= $n) {
$flag = 1;
if ($dp[$z] == -1) {
$together++;
}
$dp[$z] = 1;
$z += $i;
}
if ($flag == 1) {
$dp[$i] = 1;
$together++;
} else {
$dp[$i] = 0;
$single++;
}
}
}
if ($k <= $single) {
for ($i = 1; $i <= $n; $i++) {
if ($k != 0 && $dp[$i] == 0) {
echo $i . " ";
$k--;
}
}
} else if ($k >= $together) {
$k -= $together;
for ($i = 1; $i <= $n; $i++) {
if ($k != 0 && $dp[$i] == 0) {
echo $i . " ";
$k--;
} else if ($dp[$i] == 1) {
echo $i . " ";
}
}
} else {
echo -1;
}
}
$N = 4;
$K = 1;
findSet($N, $K);
?>
|
Time Complexity: O(N ∗ log(log(N)))
Auxiliary Space: O(N)
|
