1
$\begingroup$

I have N playing cards on which numbers are written on front as well as back.Now In one move I can flip any card so that its bottom now becomes the top.

Given the numbers on top and bottom of cards I need to find minimum number of moves that can make at least half of the cards show same number on their top.

If it is not possible to do so then also tell that it is not possible.

Example : Say we have 3 cards and represented as (number on top,number on bottom)

Card 1 : (3,10)

Card 2 : (10,3)

Card 3 : (5,4)

Now ,here minmum moves is just 1 as we can flip the first card so that number on the top becomes 10. Since two of the three cards have same number on their top (10), we do not need to change anything else, so the answer is 1.

$\endgroup$
1
$\begingroup$

If the numbers on front and back are known a priori then the answer is simple. Look at the number on the upward facing cards with the highest frequency that also can solve the problem(i.e. there are at least $\frac{n}{2}$ faces of independent cards that also have that number). Then just flip the cards that have that number face down until there are at least $\frac{n}{2}$ face up.

If $k$ is the highest frequency of such an upward facing card that can solve the problem, then it takes at most $\frac{n}{2}-k$ flips if $n$ is even and $\frac{n}{2}-k+1$ flips if $n$ is odd.

If you don't know the what the downward facing numbers are then you need to provide more information about the problem(e.g. the distribution/frequency of downward facing numbers, etc.).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Create a blue histogram $f_{up}(z)$ of the up-facing numbers, and then a red histogram $f_{dn}(z)$ of the down-facing numbers which are distinct from their up-facing alternates.

The numbers $z$ that "can solve the problem" (as @ThomasJRivera describes them) are those for which the combined blue+red frequency $f_{up}(z)+f_{dn}(z)$ is at least $n/2$, and if there are no such $z$, the task is impossible.

Of these numbers, choose a $z$ with the largest blue frequency $f_{up}(z)$. If $f_{up}(z) \ge n/2$, we are done (zero flips are required, there are already enough of these showing). Otherwise choose $\left\lceil n/2 \right\rceil - f_{up}(z)$ cards among the $f_{dn}(z)$ which have $z$ down-facing and something else up-facing and flip those. This minimizes the count of flips to attain the required up-facing frequency of at least $n/2$ for some number.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.