Number Game distribution

Правка en2, от yashsaha555, 2023-04-16 21:15:21

Jack has invited her friend Tina to play a game of numbers.The game is as follows:

There are a total of 'N' numbers (1,2,3....N) with Jack. He has to share 'X' of them with Tina. After sharing 'X' numbers, Jack has a set of '(N-X)' numbers and Tina has a set of 'X' numbers. Consider Jack's set as J and that of Tina 'T'. Now, the distribution should happen in such a way that each number from set 'J' should have a GCD of '1' from set of numbers in 'T'. Formally, GCD(x,y) = 1, where 'x' are the elements of set 'J', and 'y' are the elements of set 'T'.

Input: Value of N and X

Output: If the above condition is possible, print "Yes". Followed by (separated by SPACE), the number of components of 'T' (X number of components from set). If condition is not satisfied then print "No".

Example 1:

Input:

N = 4, X = 1

Output: Yes 3

Let us try to understand it with and example. Consider a set of N = 4 and X = 1. It means that the entire set Contains S= [1,2,3,4], and 'J' contains number from this set. He also needs to make sure that each number from his, set and Tina's set have a GCD of '1'.

By looking into the elements of the Jack's set, we can clearly see that element '2' and '4' should be in same set otherwise they will make a GCD of 2, which will ultimately not satisfy the above condition.

If we take the element '3' from the Jack's set, and give to Tina, then we can have all the conditions satisfy because the remaining element of Jack's set (1, 2, 4) will have a common GCD of 1 with the element of Tina's set which is 3.

Hence the output is : Yes 3

Example 2:

Input:

N = 6, X = 3

Output:

No

Explanation:

In this scenario, we have to give 3 elements to Tina. Initially Jack's set contains [1, 2, 3, 4, 5, 6]. The best case which we can think of is to share the prime numbers to Tina and leave the rest with Jack, or vice- versa.

In that case, Jacks's set = [2, 4, 6] Tina's set = [1, 3, 5]

But, if you see closely the element '6' and '3' will have a GCD of 3, hence the conditions will fall.

And the result will come out to be No.

Hence the output is: No

Example 3:

Input:

N = 4, X = 3

Output: Yes 1 2 4

Someone kindly solve this with explanation. Thanks.

Теги primes, coprimes

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский yashsaha555 2023-04-16 21:15:21 2 Tiny change: '= 4,\nX = 3\n\nOutput' -> '= 4,\nX = 1\n\nOutput'
en1 Английский yashsaha555 2023-04-16 21:07:15 2319 Initial revision (published)