This would give you 20 pairs. You need to have exactly K pairs. So basically for a prime number, only thing you can come up according to our solution is, 1x19 with 1+19=20 elements. Whereas with decomposing into smaller groups, we can get better answer.
Can someone tell more formal/intuitive way to state that checking till 2√k is sufficient, I understood the lower and upper bound but how it tells that checking till stated is sufficient.
And, also @gennady.korotkevich could you please explain your solution, it seems that for a particular x you are pairing it with maximum possible value from i(variables from your solution), but how this is working.
Thanks
In this approach, you are assuming that x can be a xor of only two numbers. But there may be multiple possibilities such that a^b=x.
According to my logic if n^2 >= 4 * k then output will be yes and no otherwise but i am getting WA . Can anyone tell the mistake in this logic . I am getting correct answer on given test case.
Yes I tried the same! and it gave WA…
Hi. If i take 3 X and 3 Y where X and Y are 2 no.s st X^Y=1 , i still get 9 pairs bcoz repetition of numbers is allowed . Where am I wrong
You need exactly 7 pairs and not at least 7 pairs. You can get exactly 9 pairs using 6 numbers, even exactly 8 pairs but you cannot get exactly 7 pairs using 6 numbers. You need minimum 7 numbers to get exactly 7 pairs.
Here your logic is right but if you put 1 at last and then when X=1 then XOR of 0 and1 is also 1. So it will increase extra number of pairs. You can put X+1 at last .
please explain this then why iterating till j=2rootk is optimal?