yashsaha555's blog

By yashsaha555, history, 13 months ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For similar arguments it is guaranteed any value of n>=6 there is no answer Calculate the answer for the remaining 5 numbers manually

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Let T be a set containing the number 2.
  2. All multiples of 2 (i.e. 4, 6, 8, 10, …) must also be present in set T.
  3. Numbers such as 3, 5, etc. must also be included in set T because they have a GCD > 1 with numbers in set T.

Formally,

  1. Find all prime numbers up to n/2 and let their set be P.
  2. Add all numbers that are multiples of a number present in set P, including numbers in set P, to set T. Add the remaining numbers to another set J.
  3. The number 1 can be included in either set. Consider cases of 1 separately.
  4. Sets T and J are interchangeable. If a solution exists for n,x, you can interchange the sets and give an answer for n,n-x.